会场安排问题
- 描述
- 学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动,每个时间最多安排一个活动。现在小刘有一些活动计划的时间表,他想尽可能的安排更多的活动,请问他该如何安排。
- 输入
- 第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。
随后的n行,每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间(Bi<=Ei)
- 输出
- 对于每一组输入,输出最多能够安排的活动数量。
每组的输出占一行 - 样例输入
-
2
2
1 10
10 11
3
1 10
10 11
11 20 - 样例输出
-
1
2 -
提示
注意:如果上一个活动在t时间结束,下一个活动最早应该在t+1时间开始
算法分析:
不重叠区间调度问题,一般会有三种可想到的算法:
1.在可选的工作中,每次都选取结束时间最早的工作。
2.在可选的工作中,每次都选取用时最短的工作。
3.在可选的工作中,每次都选取与最少可选工作有重叠的工作。
事实证明,只有一才是正确经得住考验的。
对于第一种算法,该算法在选取了相同数量的更早开始的工作时,其最终结束时间不会比其他方案更晚。
也就是说,最早结束的那条区间后面的数量一定大于等于其他后面区间的区间数量。
具体证明请参考:http://blog.csdn.net/luoweifu/article/details/18195607
代码如下:
#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
typedef pair<int,int>name;
name arr[10005];
int cmp(name a,name b)
{return a.second<b.second;}
int main()
{
int N,n,i,ans,t;
cin>>N;
while(N--)
{
cin>>n;
for(i=0;i<n;i++)
cin>>arr[i].first>>arr[i].second;
sort(arr,arr+n,cmp);
ans=0,t=-1;
for(i=0;i<n;i++){
if(t<arr[i].first)
{ans++;t=arr[i].second;}
}
cout<<ans<<endl;
}
return 0;
}因为sort默认对pair类型的first排序。。坑爹的,WA了一次,才意识到。
NYOJ 14 会场安排问题(也算是经典问题了)的更多相关文章
-
nyoj 14 会场安排问题(贪心专题)
会场安排问题 时间限制:3000 ms | 内存限制:65535 KB 难度:4 描述 学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办.小刘的工 ...
-
nyoj 14 会场安排问题(贪心专题)java
会场安排问题 时间限制:3000 ms | 内存限制:65535 KB 难度:4 描述 学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办.小刘的工 ...
-
基于贪心算法的几类区间覆盖问题 nyoj 12喷水装置(二) nyoj 14会场安排问题
1)区间完全覆盖问题 问题描述:给定一个长度为m的区间,再给出n条线段的起点和终点(注意这里是闭区间),求最少使用多少条线段可以将整个区间完全覆盖 样例: 区间长度8,可选的覆盖线段[2,6],[1, ...
-
nyoj 14 会场安排问题
会场安排问题 时间限制:3000 ms | 内存限制:65535 KB 难度:4 描述 学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办.小刘的工 ...
-
nyoj 题目14 会场安排问题
会场安排问题 时间限制:3000 ms | 内存限制:65535 KB 难度:4 描述 学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办.小刘的工 ...
-
NYOJ 14 场地安排(它可以被视为一个经典问题)
会场安排问题 时间限制:3000 ms | 内存限制:65535 KB 难度:4 描写叙述 学校的小礼堂每天都会有很多活动.有时间这些活动的计划时间会发生冲突,须要选择出一些活动进行举办.小刘的工 ...
-
NYOJ 14 场地安排
/* 中国标题的含义: 中国的翻译: 标题效果:寻求预定场地的最大数量,只有一个活动可以安排时间 解决问题的思路:然后使用结构数.之后再构建一个排序,排序结束时间活动.然后基于开始时间为大于一个事件的 ...
-
14.会场安排问题(L4)
时间限制:3000 ms | 内存限制:65535 KB 难度:4 描述 学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办.小刘的工作就是安排学校 ...
-
会场安排问题--nyoj题目14
会场安排问题 时间限制:3000 ms | 内存限制:65535 KB 难度:4 描述 学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办.小刘的工 ...
随机推荐
-
【ORACLE】常用脚本
--IFELSE DECLARE V_NUM NUMBER; BEGIN V_NUM := 100; IF V_NUM > 100 THEN -- ELSIF V_N ...
-
Android Studio系列教程二--基本设置与运行
Android Studio系列教程二--基本设置与运行 2014 年 11 月 28 日 DevTools 本文为个人原创,欢迎转载,但请务必在明显位置注明出处! 上面一篇博客,介绍了Studio的 ...
-
解决启动Biee控制台乱码问题
在安装完Biee后,大家都可以看到在程序中可以找到启动BI服务的地方 点击上图中的启动bi服务则在window系统中会弹出一个dos窗口,来显示执行启动服务的操作,如下图 上图显示的是正常情况,本人安 ...
-
C++ 中的名称冲突之 ";y1";
已经是第二次遇到这个问题了: #include <bits/stdc++.h> using namespace std; ); ][N][][N]; int x1, x2, y1, y2; ...
-
【Head First Javascript】学习笔记0——自己制作chm参考手册素材
变量声明:var 常量声明:const 数据格式转换: 1.转换函数 parseInt(A):把字符串A转换成整数:其中A为只包含数字的字符串 parseFloat(A):把字符串A转换成浮点数:其中 ...
-
spring源码
今天看了看spring对于视图解析的源码,发现还不是那些思想,internalResourceView里的一个渲染方法 protected void exposeModelAsRequestAttri ...
-
linux iptables扩展,脚本防火墙
netfileter:防火墙内核态ip tables:防火墙用户态(管理防火墙规则) iptables的表和链表包括不同的链,链包括大量的规则4个表: raw,mangle,nat,filter5种链 ...
-
【Unity与23种设计模式】迭代器模式(Iterator)
GoF中定义: "在不知道集合内部细节的情况下,提供一个按序方法存取一个对象集合体的每一个单元." 迭代器模式由于经常使用到 已经被现代程序设计语言纳为标准语句或收录到标准函数库中 ...
-
Avalon MM 总线
对于Avalon Master来讲,Address信号代表一个字节(8-bit)的地址.Address的值必须与字节的宽度对齐,如果要对某个word的byte写,需要首先使用byteenable信号: ...
-
通过java程序调用ant build.xml配置文件中指定的target
一.概述 通过ant实现项目的自动化部署,jar包生成,替换,tomcat关停.启动,查看项目日志: 通过java程序调用已编辑好的ant脚本build.xml配置文件中指定的target: 文中文件 ...