贪心算法之时间规划问题
贪心算法的定义：
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，
不从整体最优上加以考虑，只做出在某种意义上的局部最优解
。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
解题的一般步骤是：
1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部最优解；
4.把子问题的局部最优解合成原来问题的一个解；
问题：设有N个活动时间集合，每个活动都要使用同一个资源，比如说会议场，而且同一时间内只能有一个活动使用，每个活动都有一个使用活动的开始si和结束时间fi，即他的使用区间为[ si , fi ]，现在要求你分配活动占用时间表，即哪些活动占用该会议室，哪些不占用，使得他们不冲突，要求是尽可能多的使参加的活动最大化，即尽可能安排最多的活动。
如果我们每次都选择开始时间最早的活动，不能得到最优解：因为开始时间最早的活动可能占据时间太长导致结束时间晚。
如果我们每次都选择持续时间最短的活动，不能得到最优解：因为可能这个活动的时间可能卡在两个活动的结束和开始时。
可以用数学归纳法证明，我们的贪心策略应该是每次选取
结束时间最早
的活动。直观上也很好理解，按这种方法选择活动可以为未安排的活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。
#include<iostream>
#include<algorithm>
using namespace std;
int N;
struct arrange{
int start;
int end;
}Arrange[100010],p[100010];
bool cmp(arrange a,arrange b)
{
return a.end<b.end; //按照结束时间从小到大排序
}
int selector()
{
//num初始值为1，因为排序好的第一个活动一定会被举办
//i是记录最后一次被举办过的活动
int num=1,i=0;
p[1].start = Arrange[0].start;
p[1].end = Arrange[0].end;
for(int j=1;j<N;j++)
if(Arrange[j].start>=Arrange[i].end) //如果这个活动开始的时间大于等于上一个活动结束的时间
{
i=j; //将该活动设为当前活动
num++; //活动数量+1
p[num].start = Arrange[i].start; //p[num]来记录每个活动的开始与结束时间
p[num].end = Arrange[i].end;
}
return num;
}
int main()
{
int t,ans;
cin>>t;
while(t--) //想要测试的样例的数目
{
cin>>N; //每个样例的活动的数目
for(int i=0;i<N;i++)
cin>>Arrange[i].start>>Arrange[i].end; //存入每个活动的开始和结束时间
sort(Arrange,Arrange+N,cmp); //按照结束时间从小到大排序
ans = selector();
cout<<"The number of activities is: "<<ans<<endl;
for(int i=1;i<=ans;i++) //打印可以举办的活动的时间安排
{
cout<<"第"<<i<<"个活动的开始时间是："<<p[i].start;
cout<<" , 结束时间是："<<p[i].end<<endl;
}
}
return 0;
}
//测试样例
//1
//11
//1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14
运行结果：
1
11
1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14
The number of activities is: 4
第1个活动的开始时间是：1 , 结束时间是：4
第2个活动的开始时间是：5 , 结束时间是：7
第3个活动的开始时间是：8 , 结束时间是：11
第4个活动的开始时间是：12 , 结束时间是：14
--------------------------------
Process exited after 3.581 seconds with return value 0
请按任意键继续. . .