贪心基础证明

1.区间划分 acwing 905

按照区间右端点来排序，如果当前点能覆盖到则继续往下读，如果不能覆盖到则点数加一，该点更新为下一个区间的最右端点

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n;
 5 const int N = 1e5 + 10;
 6 
 7 // -----------------问题一：重载怎么理解？----------------------------
 8 // 定义结构体range，重载小于号按右端点排序
 9 // 结构体中保存每个区间的左端点l与右端点r
10 // range[0].l表示 输入的第1个区间的左端点，右端点的表示同理
11 struct Range
12 {
13     int l,r;
14     bool operator< (const Range &w)const
15     {
16         return r < w.r; //按区间右端点进行排序
17     }
18 }range[N];
19 
20 int main()
21 {
22     scanf("%d", &n);
23     for (int i = 0; i < n; i ++ )
24     {
25         int l,r;
26         scanf("%d%d", &l, &r);
27         range[i] = {l,r}; 
28     }
29         
30         sort(range,range + n); //区间右端点进行排序
31         
32         int res = 0,ed = -2e9; // ed表示选点下标
33         for (int i = 0; i < n; i ++ )
34         {
35             if(range[i].l > ed) //如果该点没有覆盖到下一个区间
36             {
37                 res ++;  //需要覆盖的点的数量加一
38                 ed = range[i].r;  //点的下标更新为下一个区间的右端点
39             }
40         }
41         cout << res << endl;
42 }