1205.活动安排
时限:1000ms 内存限制:10000K 总时限:3000ms
描述
Jack是一名nwpu的大一新生,对学校举办的各种活动都十分的好奇,想尽可能多的参加这些活动。Npwu每天共有N项活动,其开始结束时间分别为B[i],E[i],(i = 1,2,……N)
请问Jack一天最多能参加几项活动。当然,Jack在同一时间内只能参加一项活动,即jack参加的活动时间上不能重叠,但时间为[t1,t2],[t2,t3]的两个活动是可以同时参加的。
输入
第一行 一个整数N(1<=n<=1000)表示活动总数。
接下来N行表示各活动的起始,结束时间0<=B[i]<E[i]<24
输出
一个整数表示Jack最多能参加的活动数目。
#include <iostream>
using namespace std;
//贪心算法
int n;
int b[1001];
int e[1001];
int endcur; //当前已参加活动的结束时间,简称当前结束时间
int cnt; //当前已参加活动的数目
int main()
{
//输入数据
cin>>n;
for(int i=0; i<n; i++)
{
cin>>b[i]>>e[i];
}
//按结束时间递增排序
for(int i=0; i<n; i++)
{
for(int j=i; j<n; j++)
{
if(e[j]<e[i])
{
swap(e[i],e[j]);
swap(b[i],b[j]);
}
}
}
//贪心算法,按结束时间递增顺序遍历所有活动
//只要能参加的都参加
endcur=e[0]; //先参加第一个活动
cnt=1;
for(int i=1; i<n; i++)
{
if(b[i]>=endcur) //如果第i个活动开始时间,比当前结束时间晚/相同
{
cnt++; //这个活动可以参加
endcur=e[i]; //更新一下当前结束时间
}
else //参加不了就换下一个
{
continue;
}
}
cout<<cnt<<endl;
return 0;
}
【后记】
1.做这道题的时候,突然想起上个假期吭哧吭哧刷杭电oj的自己,那时候只自学了一点点数据结构,还没学算法,也完全没写过C++,凭着自己并不聪明的脑子硬AC出来六十来道题,印象最深的就是卡在了这道题上。现在一看,当初自己稚嫩的想法其实就是贪心算法的思想,而这道题实在是太简单了。想当初的当初,学C语言的时候,天天发愁记不住冒泡排序,现在随手即来了。
2.越想越励志,敬大三转专业的自己。