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

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示例

5

1 5

2 4

2 8

3 7

7 9

Output示例

4

【思路】

   暴力枚举肯定会超时，所以要用合适的贪心策略。把这n个区间按起点升序排好，然后用一个maxr变量记录当前能覆盖到的最右端。从前往后扫描，因为排好序之后后面区间的left一定大于等于前面区间的left，所以对于区间a[i]来说，a[i]和前面i-1个区间能产生的最大重合区间的长度就是min(maxr,a[i].right)-a[i].left，及时更新maxr即可。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 50050;

int n;
struct node {
	int l, r;
}a[maxn];

bool cmp(node x, node y) {
	if (x.l == y.l) return x.r < y.r;
	return x.l < y.l;
}

int main() {
	while (scanf("%d", &n) == 1) {
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &a[i].l, &a[i].r);
		}
		sort(a, a + n, cmp);
		int ans = 0;
		int maxr = a[0].r;
		
		for (int i = 1; i < n; i++) {
			if (a[i].r < maxr) {
				ans = max(ans, a[i].r - a[i].l);
			}
			else {
				ans = max(ans, maxr - a[i].l);
			}
			maxr = max(maxr, a[i].r);
		}
		printf("%d\n", ans);
	}
	return 0;
}