【51Nod】1091 - 线段的重叠（贪心）

FishWang

发布于 2025-08-27 12:01:11

15700

代码可运行

运行总次数：0

代码可运行

题目链接：点击打开链接

1091 线段的重叠

基准时间限制：1 秒空间限制：131072 KB 分值: 5 难度：1级算法题

关注

X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的，[10 20]和[12 25]的重叠部分为[12 20]。

给出N条线段的起点和终点，从中选出2条线段，这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠，输出0。

Input

第1行：线段的数量N(2 <= N <= 50000)。
第2 - N + 1行：每行2个数，线段的起点和终点。(0 <= s , e <= 10^9)

Output

输出最长重复区间的长度。

Input示例

Output示例

贪心思路：把线段按起点排序，维护终点的最大值并更新ans就行了。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
struct node
{
	int l,r;
}d[50011];
bool cmp(node a,node b)
{
	return a.l < b.l;
}
int main()
{
	int n;
	scanf ("%d",&n);
	for (int i = 1 ; i <= n ; i++)
		scanf ("%d %d",&d[i].l,&d[i].r);
	sort(d+1,d+1+n,cmp);
	int pos = 1;
	int ans = 0;
	for (int i = 2 ; i <= n ; i++)
	{
		if (d[i].r < d[pos].r)
			ans = max(ans , d[i].r - d[i].l);
		else if (d[i].r >= d[pos].r && d[i].l <= d[pos].r)
		{
			ans = max(ans , d[pos].r - d[i].l);
			pos = i;
		}
		else
			pos = i;
	}
	printf ("%d\n",ans);
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

include