《算法笔记》区间贪心

大概题意

给定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
",ans);

    }
    return 0;
}

区间选点问题

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