活动选择
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描写叙述
学校的大学生艺术中心周日将面向全校各个学院的学生社团开放，但活动中心同一时候仅仅能供一个社团活动使用，而且每个社团活动開始后都不能中断。如今各个社团都提交了他们使用该中心的活动计划（即活动的開始时刻和截止时刻）。请设计一个算法来找到一个最佳的分配序列，以可以在大学生艺术中心安排不冲突的尽可能多的社团活动。
比方有5个活动，開始与截止时刻分别为：
最佳安排序列为：1,4,5。
输入
第一行输入活动数目ｎ（0
输出
输出最佳安排序列所包括的各个活动（依照活动被安排的次序，两个活动之间用逗号分隔）。
演示样例输入
6
8 10
9 16
11 16
14 15
10 14
7 11
演示样例输出
1,5,4
非常经典的贪心题，首先把这一系列活动的起始时间与结束时间按结束时间升序排序，首先把第一个活动（排完序之后）纳入决策之中，然后往下扫，每当下一个活动的開始时间大于等于上一个活动的结束时间时，就将次活动纳入决策之中。扫一遍,ok 贪心完毕
#include
#include
#include
#include
using namespace std;
struct select
{
int tag;
int begin;
int end;
};
struct select act[111];
int res[111];
bool cmp(struct select x,struct select y)
{
return x.end>n;
for(i=0;i>act[i].begin>>act[i].end;
act[i].tag=i+1;
}
sort(act,act+n,cmp);
j=0;
bool a[100];
a[0]=true;
for(i=1;i=act[j].end)//贪心核心算法
{
j=i;
a[i]=true;
}
else
a[i]=false;
}
int p=0;
for(i=0;i
Original: https://www.cnblogs.com/zfyouxi/p/5412048.html
Author: zfyouxi
Title: 活动选择问题（贪心）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/547615/
转载文章受原作者版权保护。转载请注明原作者出处！