贪心算法—Problem E
题意
有多个电视节目,每个节目有不同的开始时间和结束时间。在不冲突的情况下求能完整观看的最多节目数。
解题思路
类比于课上例题,定义结构体,包含开始时间和结束时间。将输入的数据按结束时间升序排列。定义能看到的节目数和起始时间都默认为0。将第一个节目放入后,把时间改为第一个节目的结束时间。往下遍历,以此比较下一个节目开始时间与上一个节目结束时间(已赋值给time),同时计数器++。遍历完成后,得到并输出可以看的最多节目数。
感想
类比于课上例题,感觉一般,还是得进一步熟悉贪心算法。继续练习。
AC代码
#include
#include
using namespace std;
struct TvPro{
int Ti_s;
int Ti_e;
}TvPro[100];
bool cmp(struct TvPro a,struct TvPro b)
{
if (a.Ti_e>n,n)
{
inti,time=0,count=0;
for(i=0;i>TvPro[i].Ti_s>>TvPro[i].Ti_e;
}
sort(TvPro,TvPro+n,cmp);
for(i=0;i= time)
{
count++;
time = TvPro[i].Ti_e;
}
}
cout