Question

（1）代码

头文件： https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/include/chapter16/chapter16.h

产品代码： https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter16/chapter16.cpp

测试代码： https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter16/chapter16Test.cpp

（2）练习

16.1-1

https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter16/Exercise16_1_1.cpp

16.1-2

先对每个活动按照它们的开始时间从小到大排序。令初始时 i=n+1，其结束时间无限大，每次选择"结束时间比第 i 个活动的开始时间早的“的最晚开始活动

#include <iostream>
#include <algorithm>
using namespace std;

#define N 11
//一个活动用一个结点表示
struct node
{
  int id;
  int start;
  int finish;
}A[N+1];
bool cmp(node a, node b)
{
  return a.start < b.start;
}
//16.1-2
void Greedy_Activity_Selector2()
{
  //先对每个活动按照它们的开始时间从小到大排序
  sort(A, A+N+1, cmp);
  int n = N, i = -1, m;
  for(m = n; m >= 1; m--)
  {
    //找到最后一个“结束时间在第 i 个活动开始之前”的活动
    if(i == -1 || A[m].finish <= A[i].start)
    {
      //将这个活动作为执行活动
      cout<<A[m].id<<' ';
      //递归第 m 个活动执行开始之前的贪心策略
      i = m;
    }
  }
  cout<<endl;
}
/*
0 0 //虚构活动 a0
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
*/
int main()
{
  int i;
  //输入测试数据
  for(i = 0; i <= N; i++)
  {
    A[i].id = i;
    cin>>A[i].start>>A[i].finish;
  }
  Greedy_Activity_Selector2();
  return 0;
}

16.1-3

见 算法导论-16.1-3

常规算法：

针对一个特定的教室，然后做类似于 16.1 中的工作，从剩余活动中尽量多地安排活动到这个教室。如果活动安排完了，就不需要更多的教室了。如果活动没有安排完，再选择一个新的教室，做同样的工作，直到所有的活动都安排完。

这个算法的时间复杂度是 O(n^2)，稍换一个角度，就能得到一个 O(nlgn) 的算

O(lgn) 算法：

针对一个特定的活动，为它选择一个适合的教室。对所有已经选择过的教室，用一个最大堆来维护，比较的依据是在这个教室中最早开始的活动的开始时间

具体步骤是这样的：

step1：对所有活动的结束时间从小到大排序

step2：从最后一个活动开始，向第一个活动，依次针对每个活动做以下处理（1）获取堆顶元素的信息（2）如果堆顶的活动开始时间早于当前活动的结束时间，则申请一个新的教室，把活动的开始时间填入其中，再把教室作为一个结点存入堆中（3）如果堆顶的活动开始时间晚于当前活动的结束时间，就把当前活动填入堆顶元素中（4）选择下一个活动，直到所有活动都处理过