【算法】贪心算法：活动安排问题

1）活动安排问题是在所给的活动集合中选出最大的相容活动子集合。

2）主要思想是：将活动按照结束时间进行从小到大排序，挑选出结束时间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大的相容活动子集合。

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

struct ActionInfo{
	int index;
	int startTime;
	int endTime; 
} ; 

bool cmp(const ActionInfo &a, const ActionInfo &b) {
    //比较函数，作为sort的第三个参数，实现升序排序
    if (a.endTime <= b.endTime) {
        return true;
    }
    return false;
}

int main(int argc, char *argv[]) {
	int actionsGroups = 0;                          //所有的活动的组数
	cout << "请输入活动总数：" << endl; 
    cin >> actionsGroups;
    ActionInfo *act = new ActionInfo[actionsGroups];//开辟活动数组
    cout << "请依次输入活动序号、开始时间和结束时间：" << endl; 
    for (int i = 0; i < actionsGroups; i ++) {
        //输入所有活动的信息
        cin >> act[i].index >> act[i].startTime >> act[i].endTime;
    }
    
    //对所有活动按照endtime升序排序
    sort(act, act + actionsGroups, cmp);
    
    //贪心算法：
    int currentAction = 0, count = 0;               //当前符合要求的活动
    int res[100];               //此处用一个常量来定义
    res[count] = act[0].index;
    for (int j = 1; j < actionsGroups; j ++) {
        if (act[j].startTime >= act[currentAction].endTime) {
            currentAction = j;
            res[++count] = act[j].index;    //记下不冲突活动的编码
        }
    }
    //输出
    cout << "最终安排的活动序号为：" << endl; 
    for (int k = 0; k <= count; k ++) {
        cout << res[k] << ' ';
    }
    cout << endl; 
	                                
    system("pause");
    return 0;
}