算法基础之区间选点
2024-01-02 22:29:44
区间选点
-
核心思想: 贪心
-
每次只看当前的最优解
- 将所有区间按右端点排序 从小到大遍历所有区间
- 为了覆盖更多区间 取右端点作为选点
- 若两区间互相没有交集 则再取点
-
#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() { cin>>n; for(int i=0;i<n;i++) { int l,r; cin>>l>>r; range[i] = {l,r}; // cin >> range[i].l >> range[i].r; 也可以 } sort(range,range+n); int res = 0,ed = -2e9; //res为点个数 ed为当前选点的下标 for(int i=0;i<n;i++) //遍历所有区间 { if(range[i].l > ed) //左端点大于上一次取的右端点 { ed = range[i].r; //更新右端点 res ++; //个数+1 } } cout<<res; }
-
?
文章来源:https://blog.csdn.net/Pisasama/article/details/135340847
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!