题目描述
给定 N 个闭区间 [ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N,表示区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数,表示所需的点的最小数量。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
输入样例
3
-1 1
2 4
3 5
输出样例
2
题意:使用尽可能少的点覆盖几个区间
算法思想:贪心,每次都选择当前状态下的局部最优解,最后往往也收获全局最优解.
思想演绎:如何找局部最优解?即思考有两个区间的时候如何选最少的点覆盖这两个区间.可以分情况讨论
当两区间无交集时,最少需要两个点,有交集时最少只需一个点,当两区间明明有交集,却不慎选了个不在交集中的点,那一个点也不够.所以两个区间的最优解就是先把第一个区间的右端点选上,第二个区间覆盖了就不用选了,没覆盖再选第二个区间右端点.
如何把2个区间局部最优解推演到n个区间全局最优解?依样画葫芦,把n个区间按右端点从小到大排序,先把第一个区间右端点选上,遍历剩下的区间,每次都选没被之前点覆盖的区间的右端点.这些点的个数即最小值.
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range // 区间结构体
{
int l, r;
bool operator< (const Range &W)const
{
return r < W.r; // 重载<按区间右端点排序
}
}range[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);
sort(range, range + n);
int res = 0, ed = -2e9; // 用ed存储上一个定好的点的位置
for (int i = 0; i < n; i ++ )
if (ed < range[i].l)
{
res ++ ; // 只要当前区间无法覆盖上一个点的坐标就要选新的点了
ed = range[i].r;
}
printf("%d\n", res);
return 0;
}