在数轴上选择尽量最少的点，使每个区间内至少有一个点(贪心算法）

本文主要是介绍在数轴上选择尽量最少的点，使每个区间内至少有一个点(贪心算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//算法模型
给n个闭区间【a,b】,在数轴上选择尽量最少的点，使每个区间内至少有一个点。

模型分析

根据结束时间对区间进行排序，如果上一个末尾的点，比后面区间开头小了，那么就新加入一个点。

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Node
{int b, e;
}a[1005];
bool cmp(Node q, Node w)
{return q.e < w.e; 
}
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i].b >> a[i].e; }sort(a + 1, a + 1 + n, cmp);int t = -1;ll ans = 0;for (int i = 1; i <= n; i++){if (t<a[i].b)//如果比其小了{ans++;//加一个点//更新这个点t = a[i].e;}}cout << ans << endl;}

这篇关于在数轴上选择尽量最少的点，使每个区间内至少有一个点(贪心算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---