贪心 1428 活动安排问题

一时失言乱红尘 2024-02-18 23:16 48阅读 0赞

[1428 活动安排问题][1428]

基准时间限制：1 秒 空间限制：131072 KB 分值: 10 [难度：2级算法题][2]

有若干个活动，第i个开始时间和结束时间是\[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？

Input

第一行一个正整数n (n <= 10000)代表活动的个数。
    第二行到第(n + 1)行包含n个开始时间和结束时间。
    开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000

Output

一行包含一个整数表示最少教室的个数。

Input示例

3
    1 2
    3 4
    2 9

Output示例

好开森，

思路：起点从小到大排列，起点相等，终点从小到大，申请一个数组（模拟成教室），若下一个开始时间大于或等于某个教室的最后一个活动的结束时间，就更新这个教室的最晚结束时间。最后，这个数组的大小就是答案。

**\#include<iostream>  
\#include<algorithm>  
using namespace std;  
struct node  
\{  
int s,e;  
\};  
int cmp(node x,node y)  
\{  
if(x.s==y.s)  
return x.e<y.e;  
else  
return x.s<y.s;  
\}  
node a\[10001\],b\[10001\];  
int main()  
\{  
int t,m,n,i,j;  
while(~scanf("%d",&t))  
\{  
for(i=0;i<t;i++)  
\{  
scanf("%d%d",&a\[i\].s,&a\[i\].e);  
\}  
sort(a,a+t,cmp);  
m=1;  
b\[0\]=a\[0\];  
for(i=1;i<t;i++)  
\{  
for(j=0;j<m;j++)  
\{  
if(a\[i\].s>=b\[j\].e&&a\[i\].e)  
\{  
b\[j\]=a\[i\];  
a\[i\].e=0;  
break;  
\}  
\}  
if(j==m&&a\[i\].e)  
\{  
b\[m++\]=a\[i\];  
a\[i\].e=0;  
\}  
\}  
cout<<m<<endl;  
m=0;  
\}  
return 0;  
\}**

[1428]: https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428
[2]: https://www.51nod.com/onlineJudge/problemList.html#!groupId=3