区间选点
给定 \(N\) 个闭区间 \([a_i,b_i][a_i,b_i]\) ，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 \(N\) ，表示区间数。
接下来 \(N\) 行，每行包含两个整数 \(a_i,b_ia_i,b_i\) ，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。
数据范围
\(1 \le N \le 10^5\) ,
\(−10^9≤ai≤bi≤10^9−10^9≤ai≤bi≤10^9\)
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
题解
- 将区间按照右端点进行排序
- 遍历区间，如果该区间不包含所选的点（上一次选取的右端点），则选取该区间的右端点。如果包含所选的点，则跳过
- 所选点的个数即为最优解
证明
假设最优解的个数为ans个，我们使用贪心算法所求的点的个数是cnt个。需要证明ans = cnt。
Note
证明相等通常可用 a >=b && a <= b => a = b
从这个思路出发，我们就可以判断
- 因为ans是最优解，所以ans<=cnt
- cnt是每次选取的不相交区间的总数,根据贪心局部最优解则至少需要cnt个点.所以ans>=cnt
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
vector<pair<int, int>> arr;
int main()
{
int n;
arr.reserve(n);
cin >> n;
for (int i = 0; i < n; i++)
{
int left, right;
cin >> left >> right;
arr.push_back({left, right});
}
sort(arr.begin(), arr.end(),
[](const pair<int, int> &a, const pair<int, int> b)
{
return a.second < b.second;
});
int count = 0, end = -2e9;
for (int i = 0; i < n; i++)
{
if (end < arr[i].first)
{
count++;
end = arr[i].second;
}
}
cout << count;
}