【51nod-1091】线段的重叠(贪心)
2024-08-23 00:45:25
所有线段按起点从小到大排序,然后比较出最大的重叠部分。比如第i条线段和第j条线段进行比较找出重叠部分(j>i),当第j条线段的右端点<第i条线段的右端点,此时可以让i继续比较后面的线段;如果第j条线段的右端点>第i条线段的右端点,重叠部分并不会继续增大,所以需要让i+1条线段和后面的比较。
#include <bits/stdc++.h>
using namespace std;
const int N = ;
struct node
{
int l, r;
} q[N];
bool cmp(node a, node b)
{
if(a.l==b.l)
return a.r<b.r;
return a.l<b.l;
}
int main()
{
int n;
cin>>n;
for(int i=; i<n; i++)
{
scanf("%d%d", &q[i].l, &q[i].r);
}
sort(q, q+n, cmp);
int ans = -1e9;
for(int i=; i<n-; i++)
{
bool f = ;
for(int j=i+; j<n; j++)
{
int a = max(q[i].l, q[j].l);
int b = min(q[i].r, q[j].r);
ans = max(ans, b-a);
if(q[j].r>q[i].r) break;
}
}
printf("%d\n", ans);
return ;
}
最新文章
- 在OSX和Windows版本Docker上运行GUI程序
- CM添加kafka服务
- Net分布式系统之三:Keepalived+LVS+Nginx负载均衡之高可用
- 工作随笔——pre-commit钩子限制日志长度和提交的文件类型
- JNI系列——C文件中的方法调用Java中方法
- oracle-2中commit 详解
- storm0.9.0.1安装
- 注意 sizeof 中不要有复杂运算操作
- Mybatis+SpringMVC的项目环境搭建
- Hdu 3177 Crixalis&#39;s Equipment
- 转载:修改xshell中文乱码的问题(管用)
- 201521123066 《Java程序设计》第十二周实验总结
- C++ DWORD 转byte char 数组、指针
- python:爬虫获取淘宝/天猫的商品信息
- Golang初练手-多线程网站路径爆破
- HDU 4859 海岸线(最小割+最大独立点权变形)
- hbase 无法打开60010网页
- 解决stackoverflow打开缓慢的问题
- 12、Redis的事务
- Python 文件 truncate() 方法