3.区间分组 区间问题

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 100010;
 4 struct Range {
 5     int l, r;
 6 } range[N];
 7 bool cmp(Range r1, Range r2) {
 8     return r1.l < r2.l;
 9 }
10 int main() {
11     int n;
12     cin >> n;
13     for (int i = 0; i < n; i++) {
14         cin >> range[i].l >> range[i].r;
15     }
16     sort(range, range + n, cmp);
17     priority_queue<int, vector<int>, greater<int>> heap;
18     for (int i = 0; i < n; i++) {
19         Range t = range[i];
20         if (!heap.size() || heap.top() >= t.l) { //需要开一个新的组
21             heap.push(t.r); 
22         } else { //放进这个组里，更新max_r
23             heap.pop();
24             heap.push(t.r);
25         }
26     }
27     cout << heap.size() << endl;
28     return 0;
29 }