不重叠的线段

骑猪看日落 2022-06-12 06:44 170阅读 0赞

X轴上有N条线段，每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。（注：起点或终点重叠，不算重叠）。

例如： 15 15 23 23 36 36，可以选 23 23 36 36，这2条线段互不重叠。

Input

第1行：1个数N，线段的数量(2 <= N <= 10000)   
第2 - N + 1行：每行2个数，线段的起点和终点(-10^9 <= S,E <= 10^9)

Output

输出最多可以选择的线段数量。

Sample Input

3
    1 5
    2 3
    3 6

Sample Output

#include<cstdio>
    #include<cstring>
    #include<map>
    #include<set>
    #include<algorithm>
    using namespace std;
    struct A{
        int s,e;
    }f[10001];
    bool cmp(A x,A y)
    {
        return x.e<y.e;
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=0;i<n;i++)
                scanf("%d %d",&f[i].s,&f[i].e);
            sort(f,f+n,cmp);
            int e=f[0].e;
            int ans=1;
            for(int i=1;i<n;i++)
            {
                if(e<=f[i].s)
                {
                    ans++;
                    e=f[i].e;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

不重叠的线段

发表评论取消回复

还没有评论，来说两句吧...

相关阅读