35 lines
777 B
C++
35 lines
777 B
C++
#include <iostream>
|
|
#include <algorithm>
|
|
using namespace std;
|
|
const int MAXN = 5005;
|
|
struct Node {
|
|
int l, r;
|
|
} a[MAXN];
|
|
int dp[MAXN];
|
|
bool cmp(Node x, Node y) {
|
|
return x.r < y.r;
|
|
}
|
|
int main() {
|
|
int n;
|
|
cin >> n;
|
|
for (int i = 1; i <= n; i++) {
|
|
cin >> a[i].l >> a[i].r;
|
|
}
|
|
// 按结束时间排序
|
|
sort(a + 1, a + n + 1, cmp);
|
|
for (int i = 1; i <= n; i++) {
|
|
// 不选第 i 个
|
|
dp[i] = dp[i - 1];
|
|
// 找最后一个与 i 不冲突的区间
|
|
int j;
|
|
for (j = i - 1; j >= 0; j--) {
|
|
if (j == 0 || a[j].r <= a[i].l) {
|
|
break;
|
|
}
|
|
}
|
|
// 选第 i 个
|
|
dp[i] = max(dp[i], dp[j] + (a[i].r - a[i].l));
|
|
}
|
|
cout << dp[n] << endl;
|
|
return 0;
|
|
} |