活动安排问题

经典的贪心问题。

Question

假设有n个活动的集合E={a1,a2,...,an}，其每个活动都要求使用同一资源（如某个设备、教室、场地等），而在同一时间内只允许一个活动使用这一资源。

每个活动都有一个要求使用该资源的起止时间si,fi，且si<fi。如果选择了活动ai，则它在半开的时间区间[si,fi)内占有资源。两个活动ai,aj称为是相容的，当且仅当它们的时间区间[si,fi)和[sj,fj)不相交，即si>=fj 或 sj >=fi。现要求在所给定的活动集中选出最大的相容活动子集。

请补充要求的函数代码。

提示：贪心策略

输入，有多行，第1行是活动的个数n，后面n行，每行3个整数，是每个活动的编号、占用资源的开始时间、结束时间。

输出，选出的最大活动子集，即有多行，每行包括活动的编号、开始时间、结束时间。

Example

Input

Output

3：1-4
4：5-7
6：8-11
7：12-14

分析

经典的贪心问题，贪心策略为选择结束时间最早的活动，因为这样就可以给后面的活动留出更多的时间。

掉坑：在选择活动时只处理了前24小时的活动，而事实证明我画蛇添足了。

Answer

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
//定义允许的最大活动数
#define Maxn  100
//定义活动的类型
typedef  struct act_Node
{  int Id;       //活动ID
   int s_Time;   //活动开始时间
   int f_Time;   //活动结束时间
} ACND;
//对活动按贪心准则排序
void Sort(int n,ACND arr[])
{
    for(int i=0;i<n;i++){
        int tmp=i;
        for(int j=i+1;j<n;j++){
            if(arr[j].f_Time<arr[tmp].f_Time){
                tmp=j;
            }
        }
        ACND tmpSwap=arr[i];
        arr[i]=arr[tmp];
        arr[tmp]=tmpSwap;
    }
}
//进行贪心选择，得到最大相容的活动集合输出
void Select(int n,ACND arr[])
{
    int nTime=0;
    ACND*p=arr;
    while(p-arr<n){
        if(p->s_Time>=nTime){
            cout<<p->Id<<":"<<p->s_Time<<"-"<<p->f_Time<<endl;
            nTime=p->f_Time;
        }
        p++;
    }
}
int main()
{  ACND arr[Maxn];
   int an,i;
   cin>>an;           //读入活动个数
   //读入各个活动的编号和占用资源的起止时间
   for(i=0;i<an;i++)
     cin>>arr[i].Id>>arr[i].s_Time>>arr[i].f_Time;
   //对活动按贪心准则进行排序
   Sort(an,arr);
   //进行贪心选择，获得最优解并输出
   Select(an,arr);
  return 0;
}

最后修改于 2019-05-13