贪心法求解活动安排问题

​（1）贪心算法求解过程(伪代码)
​

图1

（2）活动安排选择问题

图2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Max 51
 
struct Action{
  int b;//活动开始时间
  int e;//活动结束时间
  bool operator<(const Action &s) const{//重载比较符
    return e<=s.e;
  }//按结束时间递增排序
};
 
int n=11;//活动数量
Action A[]={{0,0},{1,4},{3,5},{0,6},{5,7},{3,8},{5,9},{6,10},{8,11},{8,12},{2,13},{12,15}};
//从下标1开始，每个活动的开始结束时间
bool flag[Max];//标记活动是否被选中
int Count=0;//选中的活动数
 
void solve(){
    memset(flag,0,sizeof(flag));//初始化flag
    sort(A+1,A+n+1);
    int PreEnd=0;
    for(int i=1;i<=n;i++){
        if(A[i].b>=PreEnd){
            flag[i]=true;
            PreEnd=A[i].e;
        }
    }
}
 
int main()
{
   solve();
   printf("求解结果\n");
   printf("选取的活动：");
   for(int i=1;i<=n;i++)
       if(flag[i]){
         printf("[%d,%d] ",A[i].b,A[i].e);
         Count++;
       }
    printf("\n共%d个活动",Count);
}

时间复杂度为O(n*logn) //主要为快速排序耗时

图3

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define Max 51
 
struct Cow{
    int no;//牛编号
    int b;//产奶开始时间
    int e;//产奶结束时间
    bool operator<(const Cow &s) const{//重载比较符
        if(e==s.e)
            return b<=s.b;
        else
            return e<=s.e;
    }//优先按结束时间递增排序，若相同则按开始时间递增排序
};//定义牛的结构体
 
int n=5;//牛的数量
Cow A[]={{0,0,0},{1,1,10},{2,2,4},{3,3,6},{4,5,8},{5,4,7}};
//从下标1开始，每个牛的开始结束时间
int ans[Max];//标记每个牛的畜栏号
 
void solve(){
    sort(A+1,A+n+1);//按牛的产奶时间排序
    memset(ans,0,sizeof(ans));//初始化ans数组
    int num=1;//畜栏从1开始安排
    for(int i=1;i<=n;i++){
        if(ans[i]==0){//如果当前牛未安排畜栏
            ans[i]=num;
            int PreEnd=A[i].e;//前一个奶牛产奶结束时间
            for(int j=i+1;j<=n;j++)//安排下一头奶牛
                if(A[j].b>PreEnd&&ans[j]==0){//当前牛的开始产奶时间在上一头牛的结束产奶时间之后
                    ans[j]=num;
                    PreEnd=A[j].e;
                }
            num++;
        }
    }
}//求解
 
int main(){
    solve();
    printf("求解结果\n");
    for(int i=1;i<=n;i++)
        printf("牛%d安排到畜栏%d\n",A[i].no,ans[i]);
}

时间复杂度为O(n^2) //主要为双层循环耗时

-------该算法摘自《算法设计与分析(第2版)》