贪心--区间问题

1、区间选点问题

https://www.acwing.com/problem/content/907/

给定n个区间，选择尽量少的点使得每个区间都至少包含一个点，问最少的点的数量是多少。

 1 #include<algorithm>
 2 #include<iostream>
 3 using namespace std;
 4 const int N=1e5+10;
 5 struct range{
 6     int l,r;
 7     bool operator<(const range& t){
 8         return r<t.r;
 9     }
10 }r[N];
11 int main(void){
12     int n;
13     cin>>n;
14     for(int i=0;i<n;i++){
15         cin>>r[i].l>>r[i].r;
16     }
17     sort(r,r+n);
18     int start=-2e9,res=0;
19     for(int i=0;i<n;i++){
20         if(r[i].l>start){
21             start=r[i].r;
22             res++;
23         }
24     }
25     cout<<res;
26     return 0;
27 }

2、最大不相交的区间数量

https://www.acwing.com/problem/content/910/