You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
39 lines
1.1 KiB
39 lines
1.1 KiB
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
const int N = 5010;
|
|
|
|
struct Node {
|
|
int st, ed;
|
|
const bool operator<(const Node &b) {
|
|
return st < b.st; // 按开始时间排序
|
|
}
|
|
} a[N];
|
|
|
|
// 贪心:线段重合 求最大重叠段长度和最大间距
|
|
int main() {
|
|
#ifndef ONLINE_JUDGE
|
|
freopen("P1204.in", "r", stdin);
|
|
#endif
|
|
int n;
|
|
cin >> n;
|
|
for (int i = 1; i <= n; i++) cin >> a[i].st >> a[i].ed;
|
|
sort(a + 1, a + 1 + n);
|
|
|
|
int st = a[1].st, ed = a[1].ed;
|
|
int mx1 = ed - st; // 最长有人的时间段
|
|
int mx2 = 0; // 最长无人的时间段
|
|
|
|
for (int i = 2; i <= n; i++) {
|
|
if (a[i].st <= ed) { // 前后连接上
|
|
ed = max(ed, a[i].ed); // 更新终点ed
|
|
mx1 = max(mx1, ed - st); // 更新一下最长的有人的时间段
|
|
} else { // 前后没有接上
|
|
mx2 = max(mx2, a[i].st - ed);
|
|
st = a[i].st; // 更新起点
|
|
ed = a[i].ed; // 更新终点
|
|
}
|
|
}
|
|
printf("%d %d\n", mx1, mx2);
|
|
return 0;
|
|
} |