https://qoj.ac/contest/537/problem/1173
problem
给定 \(n\leq 10^6\) 个区间，你需要求出能够最多选出多少对区间，使得两个区间不交（区间为闭区间）。要求一个区间最多属于一对选出的区间。
solution
这是一般图匹配问题的特殊情况，所以放弃 dp，考虑贪心、网络流、匹配等。
按照左端点对所有区间排序。考虑维护两堆东西：第一堆是未匹配的区间，第二堆是已经匹配的区间对。每次加进来一个新的区间 \(c\)，如果能和未匹配区间匹配那么就匹配掉，然后加入匹配区间对。否则，考虑这个一个事情，对于匹配的区间 \(a, b(a_r<b_l)\)，现在显然加入的 \(a_r<c_l\)，如果 \(b_r<c_r\)，那么不要将 \(c\) 扔进待匹配队列中，而是匹配 \(a, c\)，准备将 \(b\) 扔进去。对 \(b\) 重复上述过程，首先它不能去匹配新的区间，因为它的 \(l\) 更小，其次它尝试去换个新的区间，这么一看其实我们使得 \(b\) 是所有符合条件中 \(r\) 最小的那个，这样 \(b\) 就换完，直接丢进未匹配区间。至于 \(c\) 不能匹配，换匹配也不优，直接丢入未匹配队列。这样以后，你发现未匹配区间不会多出新的可以匹配的区间，于是你不用管他们，算法正确。
显见使用 priority_queue 维护。两堆都按照 \(r\) 排序。
\(O(n\log n)\)
code
点击查看代码
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
int main() {
freopen("interval.in", "r", stdin);
freopen("interval.out", "w", stdout);
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
sort(a.begin(), a.end());
priority_queue<int, vector<int>, greater<int>> q1, q2;
int ans = 0;
for (auto elem : a) {
int l = elem.first, r = elem.second;
if (!q1.empty() && q1.top() < l) {
q1.pop();
ans += 1;
q2.push(r);
} else if (!q2.empty() && q2.top() < r) {
q1.push(q2.top());
q2.pop();
q2.push(r);
} else {
q1.push(r);
}
}
cout << ans << endl;
return 0;
}