贪心算法 - 选点问题 (15 分) C++

题目

数轴上有n个闭区间[ai, bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。

输入格式：

第一行一个数字n，表示有n个闭区间。 下面n行，每行包含2个数字，表示闭区间[ai, bi]

输出格式:

一个整数，表示至少需要几个点

输入样式：

在这里给出一组输入。例如：

输出样式：

在这里给出相应的输出。例如：

基本思想：

一个点要处于尽可能多的区域内

代码实现：

#include<bits/stdc++.h> using namespace std;typedef struct{int start;int end; }area;bool cmp(area a, area b) {if(a.start==b.start) return a.end<b.end;else return a.start<b.start; }int main() {int n;cin>>n;int count=0; //考虑数轴上没有闭区间的情况 //不过题目的测试点中没有这种情况，可以把count直接设成1, 省略下面这个if-else判断if(n==0){cout<<count<<endl;return 0;}else count=1;area a[n];for(int i=0; i<n; i++){cin>>a[i].start>>a[i].end;}sort(a, a+n, cmp); //因为a是结构体，要重写cmpfor(int i=0, j=0; i<n && j<n; ){if(a[i].end>=a[j].start) //a[i]和a[j]存在重叠部分//注意, 因为是闭区间,要考虑a[i].end和a[j].start相等的情况{j++;}else //a[i]和a[j]不存在重叠部分//新的a[i]为旧的a[j], 新的a[j]为旧的a[j+1], 继续循环{count++;i=j;j++;}}cout<<count<<endl;return 0; }

 提交结果：

总结

以上是生活随笔为你收集整理的贪心算法 - 选点问题 (15 分) C++的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。