题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2037

活动安排问题,可用贪心。

1、把活动按结束时间递增排序。

2、直观上,选择相对活动为未安排活动留下尽可能多的时间。

#include <cstdio>
#include <algorithm>
#include <string.h> using namespace std; struct action
{
int s;///开始时间
int f;///结束时间
int index;///活动标号
}; action a[];
bool b[]; bool cmp(const action &a,const action &b)
{
if(a.f<=b.f)
return true;
else return false;
} void GreedySelector(int n,action a[],bool b[])
{
b[]=true;///第一个活动必须选
///记录最近一次加入到集合b中的活动
int preEnd=;
for(int i=; i<n; i++)
{
if(a[i].s>=a[preEnd].f)
{
b[i]=true;
preEnd=i;
}
}
} int main()
{
int n;
while(scanf("%d",&n),n)
{
memset(b,false,sizeof(b));
for(int i=; i<n; i++)
{
scanf("%d%d",&a[i].s,&a[i].f);
///a[i].index=i;
}
sort(a,a+n,cmp);
GreedySelector(n,a,b);
int Max=;
for(int i=; i<n; i++)
{
if(b[i])
Max++;
}
printf("%d\n",Max);
/*for(int i=0;i<n;i++)
{
if(b[i])
printf("%d ",a[i].index);
}
printf("\n");*/
}
}

最新文章

  1. UIDynamic--动力元素行为:UIDynamicItemBehavior
  2. Smart3D系列教程5之 《案例实战演练2——大区域的地形三维重建》
  3. 最小系统加载工具 systemjs
  4. C++学习基础四——顺序容器和关联容器
  5. css之首字母大写 | 全部大写 | 全部小写 | text-transform
  6. atitit.ajax 最佳实践跟框架选型 o99
  7. 《ASP.NET1200例》嵌套在DataLisT控件中的其他服务器控件---DropDownList控件的数据绑定
  8. bug_ _java.lang.RuntimeException: Unable to start activity ComponentInfo{包名/类名}
  9. 纯真IP数据库导入mysql
  10. 发布mvc3的项目时system.web.mvc 版本 为3.0.0.1高于服务器版本3.0.0.0 升级到3.0.0.1
  11. FATE(费用背包,没懂)
  12. centos6.5安装rabbitmq3.6.14
  13. (NO.00005)iOS实现炸弹人游戏(四):游戏数据的初始化(一)
  14. 第五周作业--测试与版本发布(Alpha版本)
  15. week3-构造一个简单的linux系统
  16. django -- 修改admin 密码问题
  17. 1.python进程、线程、多线程
  18. python爬虫之urlError异常处理
  19. (C#)找的winform窗体自适应类
  20. ideau 2018.1.2安装和使用

热门文章

  1. JSON转C#实体类
  2. 查询指定tomcat应用的进程数
  3. 如何看linux是32位还是64位--转
  4. JS字符串与二进制的相互转化
  5. C# 面试题二
  6. sqlite3在别的目录写文件的问题
  7. log4net日记文件路径动态配置
  8. bootstrap清除数据源
  9. C# ADO.NET面向对象想法
  10. django中自定义表名及字段名称