题目描述
输入n条线段,线段可以用(x,y)表示,x是起点,y是终点。x,y均是整数且满足0<x<y<1,000,000。要求计算这些线段所覆盖的不重合区间的总长度。
样例
3
1,3
5,7
2,6
4
(贪心) $O(n)$
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int n;
struct range
{
int l, r;
bool operator< (const range& R) const {
return l < R.l;
}
}range[N];
int main()
{
ios::sync_with_stdio(false);
cin >> n;
char p;
for (int i = 0; i < n; i++) cin >> range[i].l >> p >> range[i].r;
sort(range, range + n);
int st = range[0].l, ed = range[0].r, ans = 0;
for (int i = 1; i < n; i++) {
if (range[i].l < ed) {
ans += range[i].l - st > 0 ? range[i].l - st : 0;
if (range[i].r < ed) st = range[i].r;
else {
st = ed;
ed = range[i].r;
}
}
else {
ans += ed - st;
st = range[i].l;
ed = range[i].r;
}
}
ans += ed - st;
cout << ans;
return 0;
}