本文主要是介绍区间选点问题-贪心-C++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题：
给定 𝑁 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 𝑁，表示区间数。
接下来 𝑁 行，每行包含两个整数 𝑎𝑖,𝑏𝑖，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。
数据范围
1≤N≤10^5,
−10^9≤𝑎𝑖≤𝑏𝑖≤10^9输入样例：
3 -1 1 2 4 3 5
代码：
#include<iostream>
#include<algorithm>
using namespace std;
using Pii = pair<int, int>;
const int N = 100010;
Pii Range[N];
int main(){int n;cin >> n;for (int i = 0; i < n;i++){cin >> Range[i].first >> Range[i].second;}sort(Range, Range + n, [](const Pii &a, const Pii &b) -> bool{ return a.second < b.second; });int ed = -2e9, res = 0;for (int i = 0; i < n;i++){if(Range[i].first>ed){res++;ed = Range[i].second;}}cout << res << endl;
}题解：
题意就是给你10^5以下个区间，所以我们const int N = 100010;让你在数轴上选择一些点，这些点要能覆盖得到所有的区间，当然了，数量越少越好：
以此图为例子，灰色笔画的这两个点就是答案，你再也不可能找到更少的点来覆盖每个区间了。
计算机并不容易比我们更容易地判断出结果，我们可以先排个序看看：
我们暂且以每个区间的右端点的由小而大来排序，我们如果以每个区间的右端点来设点，其实更有可能让这个点覆盖到下一个区间甚至下下一个区间，这样更可能满足要求，这是贪心的思想，即：短视地选择我们遍历的区间的右端点作为答案，然后妄想让它尽可能地覆盖下一个、下下一个点......
我们还发现：如果A区间的右端点在下一个区间（记为B）的左端点之右的话，那么我们把A区间的右端点放到答案中，它不仅可以覆盖A区间，连B区间都覆盖了，甚至满足条件它连C区间也可以给覆盖了......我们只需维护一个变量ed记为我们刚埋的点，刚开始这个ed我们赋值为负无穷，
遇到一个区间，如果它的左端点比ed还小，那说明不用管它了，ed完全可以覆盖它，否则，说明这一个区间我们ed够不着，需要在这个区间设点了，即把这个区间的右端点作为新的ed，让他去在遍历下一个区间时，看能不能不设点，ed就能覆盖下一个区间。
总之，遇到区间问题，尽量想到排序，贪心.....
参考链接：链接
这篇关于区间选点问题-贪心-C++的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
