【贪心】闭区间问题

<center>

问题 X: 【贪心】闭区间问题

时间限制: 1 Sec  内存限制: 64 MB
提交: 15  解决: 9
[提交][状态][讨论版]
</center>

题目描述

通过魔法钟回来的张琪曼和魔法学院的其他学员一起研究营救李旭琳脱离“时空陷”的方法。他们建立了n个对历史时间线的监控点,每个监控点可监控历史上的一个时间段,我们可以简单地看做是 x 轴上 n 个闭区间。但有些监控点监控的时间段是重叠的,这会干扰监控的准确性。请尝试去掉尽可能少的闭区间,使剩下的闭区间都不相交。

输入

第一行为闭区间的个数n(1≤n≤40000),随后n行为闭区间的2个端点。

输出

输出去掉尽可能少的闭区间的个数。

样例输入

3
10 20
15 10
20 15

样例输出

2
思路:由于是闭区间,比上一题增加不相交就可以。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct node{
    int begin;
    int end;
};
node tt[105];

int cmp(node a,node b){
    return a.end<b.end||a.end==b.end&&a.begin<b.begin;
}

int main()
{
    int n;
    int t;
    int s=0;
    int k;//记录上一个计入的节目。
    //while(scanf("%d",&n)!=EOF&&n){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d %d",&tt[i].begin,&tt[i].end);
            if(tt[i].begin>tt[i].end){
                t=tt[i].begin;
                tt[i].begin=tt[i].end;
                tt[i].end=t;
            }
        }
        sort(tt,tt+n,cmp);
        s+=1;
        k=0;
        for(int i=1;i<n;i++){
            if(tt[i].begin>tt[k].end){
                s++;
                k=i;
            }
        }
        printf("%d\n",n-s);
        s=0;
    //}

    return 0;
}

 

 
全部评论

相关推荐

昨天 20:51
门头沟学院 golang
点赞 评论 收藏
分享
头像
03-14 11:23
已编辑
北京邮电大学 管理咨询
211勇闯初创小公司头破血流系列3这件事不是发生在我身上的,但前同事们参与创作的积极性空前高涨,为了习惯,还是都采用第一人称的视角来看这出大戏。有一天老板在我们的眼皮底下接了一个电话,最终敲定了去北京出差的时间,下周一。他得意洋洋地说,这单下来保底五百万的流水,如果成了,我们都能得到五位数的提成。这对于一群刚上班的人来说是天大的诱惑,我们经历了周末的无偿加班,把他去北京所需要的文件都准备好了。只是在去北京的周一当天,老板睡过头了。整个上午都没见他的踪影,给他发文件也不会,打电话问问题也不接,直到中午才姗姗来迟。当然,这只是拉开了这场恐怖出差的序幕。只见他来了也不紧不慢的,手指在办公室转了一圈,...
姜大力:补充: 1.五百万的单子根本没有五百万,只是过去展示拼装的产品并简单考察。该项目只是竞标,项目内容是商业街区改造; 2.决策是当天上午10点半左右老板珊珊来迟后突发奇想去北京,中午1点在催促下着急出发,没有任何出差补助; 3.出发之前已经知道进京证不好使了,但还是执意要开车去; 4.实习生实打实连续开了***小事车,非常辛苦,工资在转正后只有两千五; (有疑问会继续补充)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务