4.区间覆盖区间问题

 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 st, ed;
12     cin >> st >> ed;
13     int n;
14     cin >> n;
15     for (int i = 0; i < n; i++) {
16         cin >> range[i].l >> range[i].r;
17     }
18     sort(range, range + n, cmp);
19     bool success = false;
20     int res = 0;
21     for (int i = 0; i < n; i++) {
22         //用双指针算法扫描一遍
23         int j = i, r =-2e9;
24         while (j < n && range[j].l <= st) {
25             r = max(range[j].r,  r);
26             j++;
27         }
28         /*
29         上面扫描的作用就是找到：
30         所有左端点在st的左边的所有区间里面
31         右端点的最大值是多少
32         */
33         res++;
34         if (r < st) {
35             res = -1;
36             break;
37         }
38         st = r;
39         if (st >= ed) {
40             success = true;
41             break;
42         }
43         i = j - 1;
44     }
45     if (!success) {
46         res = -1;
47     }
48     cout << res << endl;
49     return 0;
50 }
4.区间覆盖 区间问题

4.区间覆盖区间问题
