1.区间选点 区间问题

 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.r < r2.r;
 9 }
10 int main() {
11     int n;
12     cin >> n;
13     for (int i = 0; i < n; i++) {
14         int l, r;
15         cin >> l >> r;
16         range[i] = {l, r};
17     }
18     sort(range, range + n, cmp);
19     int res = 0, ed = -2e9;
20     //ed表示上一个点的下标
21     for (int i = 0; i < n; i++) {
22         if (range[i].l > ed) {
23             res++;
24             ed = range[i].r;
25         }
26     }
27     cout << res << endl;
28     return 0;
29 }