首页 > 代码库 > 贪心入门——活动安排问题
贪心入门——活动安排问题
贪心入门的几个例题来自51nod
问题描述
有若干个活动,第i个开始时间和结束时间是[Si,fi),只有一个教室,活动之间不能交叠,求最多安排多少个活动?
输入
第1行:1个数N,线段的数量(2 <= N <= 10000)
第2 - N + 1行:每行2个数,线段的起点和终点(-10^9 <= S,E <= 10^9)
输出
输出最多可以选择的线段数量。
输入示例
3
1 5
2 3
3 6
输出示例
2
求解思路
按照活动的结束时间早的优先
算法代码
#include <stdio.h> typedef int Elemtype; struct time { Elemtype start; Elemtype end; }mtime[10000]; void Sort(time mtime[],int n); int Count(time mtime[],int n); int main() { int n; scanf("%d",&n); int i = 0; for(i=0;i<n;i++) { scanf("%d%d",&mtime[i].start,&mtime[i].end); } Sort(mtime,n); printf("%d",Count(mtime,n)); return 0; } void Sort(time mtime[],int n) { int i = 0,j=0; struct time temp; for(i=0;i<n-1;i++) { for(j=i+1;j<n;j++) { if(mtime[i].end > mtime[j].end) { temp = mtime[i]; mtime[i] = mtime[j]; mtime[j] = temp; } } } int Count(time mtime[],int n) { Elemtype s=0; int i = 0; int num = 1; while(i<n) { s = i;//前一个的结束作为下一个的开始标志 while((mtime[s].end > mtime[i+1].start) && (i < n)) { i++; } if(i < n) { i = i+1; num++; } } return num; }
贪心入门——活动安排问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。