凌乱的yyy/线段覆盖

003 P1803 凌乱的yyy / 线段覆盖

凌乱的yyy / 线段覆盖

题目背景

快 noip 了，yyy 很紧张！

题目描述

现在各大 oj 上有

个比赛，每个比赛的开始、结束的时间点是知道的。

yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。

所以，他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加

个及以上的比赛。

输入格式

第一行是一个整数

 ，接下来

行每行是

个整数

(

)，表示比赛开始、结束的时间。

输出格式

一个整数最多参加的比赛数目。

样例输入

3

0 2

2 4

1 3

样例输出

2

提示

对于

的数据，

。

对于

的数据，

。

对于

的数据，

。

对于

的数据，

，

。

解题思路

1.区间贪心策略，当前结束，希望找下一个区间是开始在当前区间结束后并且结束最早的

2.由1可知，可以按区间结束时间排序

参考程序

#include

using namespace std;

struct se{//区间开始时间和结束时间

int start;

int end;

};

bool cmp(se se1,se se2){//按区间结束排序规则

return se1.end

}

se ses[1000001];//区间数组

int main(){

int n;

cin>>n;

for(int i=1;i

cin>>ses[i].start;

cin>>ses[i].end;

}

sort(ses,ses+n+1,cmp);//按区间结束时间从小到大排序

int endTemp=ses[1].end;//记录第1个区间结束时间

 int ans=1;//累加第1个区间

for(int i=2;i

if(endTemp

endTemp=ses[i].end;//记录上一个区间结束时间

ans++;//由于按区间结束时间从小到大排序，因此每次找到的下一区间都是结束最早的

}

}

cout

}

2023暑假班数学思维大纲

●高斯算法    ●图中填数    ●算式谜语    ●平均数问题        ●植树问题

●妙算技巧    ●拆数技巧    ●页码问题    ●高级鸡兔同笼     ●年龄问题

●行程问题    ●行走路线问题    ●组合图形   ●工程问题   ●整除与剩余问题

●周期问题    ●天平问题     ●买卖问题    ●非十进制    ●牛吃草

说明:实际课程根据上课进度略有调整。