A.Activity planning
2018-12-04 07:14:57来源:博客园 阅读 ()
题目描述
There is a collection of n activities E={1,2,..,n}, each of which requires the same resource, such as
a lecture venue, etc., and only one activity at a time Use this resource. Each activity i has a start
time of si and an end time of fi and si<fi. If the activity i is selected, it occupies resources within
the time interval [si,fi). If the interval [si,fi) does not intersect the interval [sj,fj), then the activity i is
said to be compatible with the activity j. That is, when fi<=sj or fj<=si, the activity i is compatible
with the activity j . Choose the largest collection of activities that are compatible with each other.
输入格式
The first line is an integer n;
The next n line, two integers per line, si and fi.
输出格式
Excluding mutual and compatible maximum active number.
样例输入1
4
1 3
4 6
2 5
1 7
样例输出1
2
数据范围与提示
1<=n<=1000
这道题解法与杭电今年暑假不AC解法相同,采用贪心法
代码实例
#include<stdio.h> struct huodong { int begin; int end; } J[1002]; int main() { int n,i,j,sum,temp; sum = 1; scanf("%d",&n); for(i=0; i<n; i++) scanf("%d %d",&J[i].begin,&J[i].end); for(i=0; i<n-1; i++) { for(j=0; j<n-i-1; j++) { if(J[j].end>J[j+1].end) { temp = J[j].end; J[j].end = J[j+1].end; J[j+1].end = temp; temp = J[j].begin; J[j].begin = J[j+1].begin; J[j+1].begin = temp; } } } temp = J[0].end; for(i=1; i<n; i++) { if(J[i].begin>=temp) { sum++; temp = J[i].end; } } printf("%d\n",sum); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- P1358 扑克牌 2020-05-06
- 博弈--巴什博弈 2020-04-24
- Z 字形变换 2020-04-14
- [题记-并查集] 合根植物 - 蓝桥杯 2020-04-07
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash