《算法笔记》区间贪心

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《算法笔记》区间贪心，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含909字，纯文字阅读大概需要2分钟。

内容图文

大概题意

给定N个开区间，从中尽可能选择多的开区间，使得这些开区间两两没有交集

思路

如果有区间包含的情况，则选择小的区间，能容纳更多不包含的区间
去除区间包含的情况，将所有区间按照左端点从大到小排序，总是选择左端点最大的区间

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=11;
struct Inteval{
    int x,y;
}I[maxn];

bool cmp(Inteval a,Inteval b)//将区间排序
{
    if(a.x!=b.x) return a.x>b.x;//将左端点从大到小排序
    else return a.y<b.y;//左端点相同，则将右端点从小到大排序
}
int main()
{
    int n;//给n个开区间
    while(scanf("%d",&n),n!=0)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&I[i].x,&I[i].y);
        }
        sort(I,I+n,cmp);
        int ans=1,lastX=I[0].x;//lastX记录上一个被选中的左端点
        for(int i=1;i<n;i++)
        {
            if(I[i].y<=lastX)
            {
                ans++;
                lastX=I[i].x;
            }

        }
        printf("%d\n",ans);

    }
    return 0;
}

区间选点问题

给出N个闭区间，最少需要确定多少个点，使每个闭区间至少有一个点
思路与区间不相交问题类似，选左端点即可
将上述代码中I[i].y<=lastX改为I[i].y<lastX

内容总结

以上是互联网集市为您收集整理的《算法笔记》区间贪心全部内容，希望文章能够帮你解决《算法笔记》区间贪心所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---