51nod 1091 线段的重叠 （贪心）

51nod 1091 线段的重叠

题目

给出 $n$ 条线段，问任意两条线段最大重叠区间长度。$n<5e4$

分析

贪心，先按起点升序，终点降序排序，之后扫一遍所有区间。由于按起点升序，所以后面的区间起点一定小于前面的，因此对于当前区间，维护出现过的最远右端点 $pos$，考虑吧 $pos$ 与当前区间的相对位置跟新答案即可。 $O(logn+n)$

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 0x3f3f3f3f; const int N = 5e4 + 10; int n; struct node { int x, y; bool operator < (const node& b) const { if(x == b.x) return y > b.y; return x < b.x; } }a[N]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i].x >> a[i].y; } sort(a, a + n); int limit = -1, ans = 0; for (int i = 0; i < n; i++) { if (limit >= a[i].y) { ans = max(ans, a[i].y - a[i].x); } if(limit > a[i].x && limit < a[i].y) { ans = max(ans, limit - a[i].x); } limit = max(limit, a[i].y); } cout << ans << "\n"; }