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 }