T1：录制节目
可以将原题转化成
有 \(n\) 条线段，可以保留若干条线段，并且可以分成两部分，使得每部分的线段互不相交
先将所有线段按右端点做升序排序，且按左端点做降序排序
然后维护两个变量 last1 和 last2
last1：第一个部分的最后的端点
last2：第二个部分的最后的端点
尽量让 \(\min(\operatorname{last1}, \operatorname{last2})\) 更小
原题：P2255
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
struct line {
int l, r;
bool operator<(const line& o) const {
if (r == o.r) return l > o.l;
return r < o.r;
};
};
int main() {
int n;
cin >> n;
vector<line> d(n);
rep(i, n) cin >> d[i].l >> d[i].r;
sort(d.begin(), d.end());
int ans = 0;
int last1 = 0, last2 = 0;
for (auto [l, r] : d) {
if (last1 < last2) swap(last1, last2);
if (l >= last1) {
ans++;
last1 = r;
}
else if (l >= last2) {
ans++;
last2 = r;
}
}
cout << ans << '\n';
return 0;
}