不重叠的线段

骑猪看日落 2022-06-12 06:44 169阅读 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

2

#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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，169人围观）

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

相关阅读

相关 Fragment重叠的解决办法

这个方法确实简单暴力该BUG在support-v4 24.0.0+以上官方已修复原文：[http://www.jianshu.com/p/c12a98a36b2b][h

客官°小女子只卖身不卖艺/ 2022年09月27日 12:30/ 0 赞/ 178 阅读

相关 tableviewcell addsubview的重叠问题

关于tableview的重用机制导致子视图重叠的问题，一般都是因为子视图重复创建了，究其原因，就是重用机制没有理解透彻。这里提供两种解决方案，解决该问题的方法很多，这里只是

迈不过友情╰/ 2022年09月17日 13:15/ 0 赞/ 134 阅读

相关定位元素的重叠

上篇我已经说了，position的元素都是漂浮起来的，肯定会发生一些重叠的现象，但是到底是谁覆盖了谁，又是谁伤害了谁呢？嘻嘻，当然正常情况下有先来后到之分，不过是后来的覆盖先到

傷城~/ 2022年07月15日 02:00/ 0 赞/ 137 阅读

相关 51 nod 1091 线段的重叠

[1091 线段的重叠][1091] 基准时间限制： 1 秒空间限制： 131072 KB X轴上有N条线段，每条线段包括1个起点和终点。线段的

爱被打了一巴掌/ 2022年06月16日 12:46/ 0 赞/ 144 阅读

相关窗口重叠

书籍《CCF 中学生计算机程序设计》江涛等给定两个窗口左右上下的坐标，求重叠的面积。 //left right top bottom incl

Love The Way You Lie/ 2022年06月16日 02:36/ 0 赞/ 217 阅读

相关不重叠的线段

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

骑猪看日落/ 2022年06月12日 06:44/ 0 赞/ 170 阅读

相关线段的重叠

X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的， 1020 1020和 1225 1225的重叠部分为 1220 1220。给出N条线段的起点和终点，

男娘i/ 2022年06月12日 06:44/ 0 赞/ 227 阅读

相关线段的重叠(贪心)

线段的重叠(贪心) 描述 X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的，\[10 20\]和\[12 25\]的重叠部分为\[12 20\]。

ゞ浴缸里的玫瑰/ 2022年05月15日 03:12/ 0 赞/ 204 阅读

相关不重叠的线段(贪心)

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

﹏ヽ暗。殇╰゛Y/ 2022年05月15日 02:46/ 0 赞/ 200 阅读

相关 echarts 重叠而不堆叠

on绑定响应事件 //点击事件 daysChart.on('click', function (param) { loadOneDay(pa

太过爱你忘了你带给我的痛/ 2022年04月23日 05:22/ 0 赞/ 374 阅读