笔试算法刷题

猿辅导2021校园招聘笔试(算法一) 

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推,求职就业一站解决_牛客网 (nowcoder.com)

第一眼看到这个题想到的是蓝桥杯飞机降落,贪心题。但是这样算的是最大不相交区间数量,仔细看题是要求最多有几个区间重叠。

然后想到了,差分,然后求前缀和可以知道每个点被选中了多少次,但是看数据范围是1e9,行不通。

看数据范围是2e5,我们只能找找有什么性质了。

那么能不能对一个时间段,存进所有重合的时间段呢?判断重合需要比较左右两边很麻烦,因此我们先把时间段按照开始时间进行排序。这样我们只需要比较当前l和上一个的r就可以了。

那么,我们存当前的r,往后找,如果当前的l比r要大就说明不重合,那么后面全都不重和,把当前r丢掉就行。否则,说明重合存入。也就是说在一个r被丢掉之前,存进的都是与之重合的边界,我们取最大值即可。

同时数据2e5,也就是nlogn,每次用最小的r,很容易想到小根堆。注意c++,优先队列默认是大根堆,std::priority_queue<int,std::vector<int>,std::greater<int>> q;小根堆加参数即可。

同时为什么这样可以找到重叠的所有呢?因为当前r不是固定的,有更小的就会替换当前的,这是一个动态更新的过程。

#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;

#define fir first
#define sec second

using PII=std::pair<int,int> ;
using ari=std::array<int,3>;
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-9;

int n,m;
struct node{
	int l,r;
}a[N];
bool cmp(node a,node b)
{
	if(a.l!=b.l) return a.l<b.l;
	else return a.r<b.r; 
}
void solve()
{
	std::cin>>n;
	for(int i=1;i<=n;i++)
	{
		std::cin>>a[i].l>>a[i].r;	
	} 
	std::sort(a+1,a+1+n,cmp);
	
	int ans=0;
	std::priority_queue<int,std::vector<int>,std::greater<int>> q;//小根堆 
	for(int i=1;i<=n;i++)
	{
		while(q.size()&&a[i].l>=q.top())
		{
			q.pop();
		}
		q.push(a[i].r);
		ans=std::max(ans,(int)q.size());
	}
	std::cout<<ans<<'\n';
}
signed main()
{
    //freopen("a","w",stdout);//把结果输出到a.in里面
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t=1;
    //std::cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

突然意识到事情严重性,不会敲板子了,只能写点思维题。。。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/790509.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

docker笔记2

docker笔记2 一、阿里云镜像配置二、docker基本原理1.docker是如何启动一个容器的2.docker的底层原理 三、镜像命令总结 一、阿里云镜像配置 配置镜像的目的 由于Docker Hub等公共镜像仓库的服务器可能位于国外&#xff0c;直接从中拉取镜像时可能会遇到网络延迟或不稳定的问…

MySQL Undo Log

总结自bojiangzhou undo log称为撤销日志或回滚日志。在一个事务中进行增删改操作时&#xff0c;都会记录对应的 undo log。在对数据库进行修改前&#xff0c;会先记录对应的 undo log&#xff0c;然后在事务失败或回滚的时候&#xff0c;就可以用这些 undo log 来将数据回滚到…

(2024,测试时训练(TTT),线性注意力,RNN,嵌套循环)学习(在测试时学习):具有表达性隐藏状态的 RNN

Learning to (Learn at Test Time): RNNs with Expressive Hidden States 公和众与号&#xff1a;EDPJ&#xff08;进 Q 交流群&#xff1a;922230617 或加 VX&#xff1a;CV_EDPJ 进 V 交流群&#xff09; 目录 0. 摘要 1. 简介 2. 方法 2.1 使用 TTT 更新隐藏状态 2.2 …

常用的JVM启动参数

JVM的启动参数有很多&#xff0c;但是我们平常能用上的并不是特别多&#xff0c;这里介绍几个我们常用的&#xff1a; 1. 堆设置&#xff1a; 。 -Xms&#xff1a;设置堆的初始大小。 。.-Xmx&#xff1a;设置堆的最大大小。 2. 栈设置&#xff1a; 。 -XsS&#xff1a;设置每个…

​​​防御第一次作业

1、拓扑图及实验要求&#xff1a; 2、配置&#xff1a; 配置终端及服务器IP地址&#xff1a; Pc2&#xff1a; Client1&#xff1a; Pc4&#xff1a; Client2&#xff1a; PC1&#xff1a; Server1&#xff1a; Server2&#xff1a; 防火墙基础配置&#xff1a; [fw1]int g …

光学、SAR卫星影像助力洞庭湖决堤抢险(附带数据下载)

​​ 点击下方全系列课程学习 点击学习—>ArcGIS全系列实战视频教程——9个单一课程组合系列直播回放 点击学习——>遥感影像综合处理4大遥感软件ArcGISENVIErdaseCognition 7月5日下午&#xff0c;湖南岳阳市华容县团洲乡团北村团洲垸洞庭湖一线堤防发生决口&#xff0…

怎样在 PostgreSQL 中优化对 UUID 数据类型的索引和查询?

文章目录 一、UUID 数据类型概述二、UUID 索引和查询的性能问题三、优化方案&#xff08;一&#xff09;选择合适的索引类型&#xff08;二&#xff09;压缩 UUID&#xff08;三&#xff09;拆分 UUID&#xff08;四&#xff09;使用覆盖索引&#xff08;五&#xff09;优化查询…

Meta发布Llama 2驱动的AI代码生成器:Code Llama,开源来袭!

Meta 刚刚了号称是编程领域 “最先进的大语言模型”—— Code Llama &#xff0c;可根据 代码和自然语言提示 生成代码和有关代码的自然语言&#xff0c;支持多种主流编程语言&#xff0c; 包括 Python、C、Java、PHP、Typescript (Javascript)、C# 和 Bash 。 Code Llama 完全…

“Pandas数据处理与分析:实用技巧与应用“

目录 # 开篇 1. pandas的series的了解 1.1 pd.Series 创建 1.2 pd.series 的索引使用 1.3 pd.series 之字典/索引 1.4 pandas 转换数据类型 1.5 pandas 通过索引或者通过位置来取值 1.6 pandas 指定行取值 1.7 pands之Series 切片和索引 1.8 pands之Series 的索引和值…

vue2/3代码格式化问题,看着太难受了

1.原本的代码&#xff1a; 格式化后的代码&#xff1a; 太难受了&#xff01; 2.原本的代码 格式化后的代码 格式化跟有病似的&#xff0c;看着非常难受&#xff01; 有没有什么插件解决&#xff01;&#xff1f;

C++ //练习 14.44 编写一个简单的桌面计算器使其能处理二元运算。

C Primer&#xff08;第5版&#xff09; 练习 14.44 练习 14.44 编写一个简单的桌面计算器使其能处理二元运算。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim 代码块 /**********************************************************…

Cesium中实现全球体积云效果的一种方案

原生 Cesium 提供了一种积云的效果&#xff0c;云的物理特征和渲染性能都还不错&#xff0c;这种方案适合表达小范围相对离散的云朵&#xff0c;但是用来实现全球范围下相对连续、柔和渐变的云层比较困难。本文在体渲染的基础上&#xff0c;参考了开源社区中 shadertoy 和 thre…

java数组之线性查找、二分法查找

一、线性查找 思想&#xff1a;如果想在一个数组中查找是否有某个元素&#xff0c;最容易想到的办法就是遍历数组&#xff0c;将数组中元素与想要查找的元素逐个对比&#xff0c;如果相等表示找到了&#xff0c;如果不等&#xff0c;则表示没找到。这就是线性查找的思想。 案例…

如何在微信小程序中对接微信支付

个人名片 &#x1f393;作者简介&#xff1a;java领域优质创作者 &#x1f310;个人主页&#xff1a;码农阿豪 &#x1f4de;工作室&#xff1a;新空间代码工作室&#xff08;提供各种软件服务&#xff09; &#x1f48c;个人邮箱&#xff1a;[2435024119qq.com] &#x1f4f1…

流模型flow

流模型 Flow 超详解&#xff0c;基于 Flow 的生成式模型&#xff0c;从思路到基础到公式推导到模型理解与应用&#xff08;Flow-based Generative Model&#xff09;_generative flows-CSDN博客

软考《信息系统运行管理员》-3.1信息系统设施运维的管理体系

3.1信息系统设施运维的管理体系 1 信息系统设施运维的对象 基础环境 主要包括信息系统运行环境(机房、设备间、配线室、基站、云计算中心 等)中的空调系统、供配电系统、通信应急设备系统、防护设备系统(如消防系统、安全系统) 等&#xff0c;能维持系统安全正常运转&#xf…

食物链之带权并查集解法

直接看题&#xff1a;https://www.acwing.com/problem/content/description/242/ 下面就是代码的实现了&#xff0c;因为自己与自己肯定是同类我们初始化为0. 下面是AC代码&#xff1a; #include<bits/stdc.h> using namespace std; int n,k; int fk,x,y; int fa[10001…

C++ STL IO流介绍

目录 一&#xff1a;IO流的继承关系&#xff1a; 二&#xff1a;输入输出功能 1. 基本用法 2. 格式化输入 3.非格式化输入 4. 格式化输出 三&#xff1a;流 1. 字符流 2. 向字符流中写入数据 3. 从字符流中读出数据 4. 清空字符流 5.完整的例子 四&#xff1a;文件…

RISC-V异常处理流程概述(2):异常处理机制

RISC-V异常处理流程概述(2):异常处理机制 一、异常处理流程和异常委托1.1 异常处理流程1.2 异常委托二、RISC-V异常处理中软件相关内容2.1 异常处理准备工作2.2 异常处理函数2.3 Opensbi系统调用的注册一、异常处理流程和异常委托 1.1 异常处理流程 发生异常时,首先需要执…

生物打印后的生物力学过程

生物打印后的生物力学过程 3D生物打印技术在组织工程领域展现出巨大的潜力&#xff0c;但打印后组织的生物力学特性对其最终成功至关重要。本文将详细介绍打印后组织的生物力学特性及其在组织工程中的应用。 1. 打印后水凝胶交联 原位交联可以在生物打印过程中提供足够的机械…