区间

链接

题意:给定n个区间[li,ri]。你可以选出任意一些区间,设选出的区间个数是s,[l,r]是这些区间的交,求min(s,r-l+1)的最大值。 N≤3×105

分析:首先按照左端点排序,然后依次加入每条线段。加入后判断min(s, r-l+1)哪个大。如果s大,那么说明答案受限制与区间交,所以可以考虑去掉一些线段,去掉右端点最小的(堆维护);如果s小,那么继续加入线段即可。

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ;
struct Edge{
int l, r;
bool operator < (const Edge &A) const { return l < A.l; }
} A[N];
priority_queue<int, vector<int>, greater<int> > q; int main() {
int n = read();
for (int i = ; i <= n; ++i) A[i].l = read(), A[i].r = read();
sort(A + , A + n + );
int ans = , cnt = ;
q.push(A[].r);
for (int i = ; i <= n; ++i) {
cnt ++;
q.push(A[i].r); ;
ans = max(ans, min(cnt, q.top() - A[i].l + ));
while (!q.empty() && q.top() - A[i].l + < cnt) {
cnt --;
q.pop();
ans = max(ans, min(cnt, q.top() - A[i].l + ));
}
ans = max(ans, min(cnt, q.top() - A[i].l + ));
}
cout << ans;
return ;
}

最新文章

  1. Programming in lua 杂记(转)
  2. Android 杀死进程
  3. ZooKeeper系列2:ZooKeeper的运行
  4. java 8-5 抽象
  5. java面试问道的
  6. NoSQL分类
  7. 用任务管理器画CPU正弦曲线
  8. softmax
  9. ActionBarActivity &amp; FragmentActivity
  10. Arduino101 中使用 Mirf 库的问题(2016-04-04)
  11. C++ Primer Plus 6 第一章
  12. ROS_Kinetic_24 使用catkin_create_qt_pkg快速创建qt-ros功能包
  13. H5学习之旅-H5的样式(5)
  14. SQL Server同一表不同列数据同步
  15. 一个python小爬虫
  16. 28.TreeSet
  17. 移动应用调试之Inspect远程调试
  18. 用网线直连的两台PC上的虚拟机通过网线通信的配置
  19. shell 判断为空打印
  20. STL中优先队列的使用

热门文章

  1. js判断状态
  2. Vue的路由
  3. 教你如何获取ipa包中的开发文件
  4. 使用keychain永久存储数据
  5. sonarQube环境搭建--常见问题及解决
  6. python3 django1.10 使用mysql服务器
  7. 铁乐学python_day20_面向对象编程2
  8. Bootstrap后台管理框架
  9. Mysql 安装服务无法启动解决方案与使用的一般使用指令
  10. 个人技术博客二之apk反编译与加密