区间选点问题-贪心-C++

本文主要是介绍区间选点问题-贪心-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;让你在数轴上选择一些点，这些点要能覆盖得到所有的区间，当然了，数量越少越好：

以此图为例子，灰色笔画的这两个点就是答案，你再也不可能找到更少的点来覆盖每个区间了。

计算机并不容易比我们更容易地判断出结果，我们可以先排个序看看：
我们暂且以每个区间的右端点的由小而大来排序，我们如果以每个区间的右端点来设点，其实更有可能让这个点覆盖到下一个区间甚至下下一个区间，这样更可能满足要求，这是贪心的思想，即：短视地选择我们遍历的区间的右端点作为答案，然后妄想让它尽可能地覆盖下一个、下下一个点......