给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。
数据范围
1≤N≤10^5,
−10^9≤ai≤bi≤10^9
输入样例：
1. 3 2. -1 1 3. 2 4 4. 3 5
输出样例：
2
思路：区间问题大多是数学问题，先排序，不过这里是以(a,b)中的b为基准排序，从小到大排，然后每次选择b值，这样可以保证覆盖的区间最多
如图，如果我们选择1中的最右边那个点，那么就可以保证2和3这个区间也被覆盖
完整代码 ：
#include <iostream> #include <algorithm> using namespace std; int n; const int N=1e5+10; struct range{ int l,r; bool operator< (const range &w)const{ return r<w.r; } }; range range[N]; int main(){ cin>>n; for(int i=0;i<n;i++)cin>>range[i].l>>range[i].r; sort(range,range+n); int count=0,temp=-2e9; for(int i=0;i<n;i++) { int temp=range[i].r; count++; while(temp>=range[i+1].l&&temp<=range[i+1].r)i++; } cout<<count; }
