算法作业十（贪心算法）

1.问题
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。
目标是尽可能选择更多的会议来使用资源。
2.解析
1.选择最早开始时间且不与已安排会议重叠的会议
2.选择使用时间最短且不与已安排会议重叠的会议
3.选择最早结束时间且不与已安排会议重叠的会议
三个贪心策略中应该选择第三个，因为在这道题的情景之下，贪心的对象应该转化为使剩余时间的可安排时间段尽可能大，以便之后的会议能够有更多的时间来进行。
3.设计

//A存储的是成对信息 A[i]代表的是第i个会议
//有两个属性，begin开始时间，end结束时间
//num代表的是一共有多少个会议
ARRANGE_MEETING(A,num)
    SORT_ASC(A) //根据end结束时间进行降序排序，如果end相同，则根据begin来进行排序
    NOW_END = A[0].end //选择第一个会议
    CNT=1 //记录选择了几个会议
    for i = 1 to num:
        if A[i].begin >= NOW_END:
            NOW_END = A[i].end
            CNT++
    return CNT;

4.分析
1.时间复杂度由两部分构成，分别是排序所需要的时间以及遍历一遍所需要的时间。
排序的复杂度跟采用的算法有关，如果采用冒泡排序，那么复杂度为O(n2);如果采用的是快速排序，那么排序部分复杂度为O(nlog(n))。
遍历一遍所用的时间为O(n)。
因为这里直接用的是STL中的快速排序，所以总体的时间复杂度为:O(nlog(n))
2.因为空间只用了一个变量，所以空间复杂度为O(1) 。
5.完整代码

#include <bits/stdc++.h>
const int maxn = 1000;
using namespace std;
int num;
struct meeting
{
    int b_time;
    int e_time;
    meeting()
    {
        b_time = 0;
        e_time = 0;
    }
};

meeting m[maxn];
queue<meeting> record;

bool cmp(meeting m1, meeting m2)
{
    if(m1.e_time == m2.e_time)
        return m1.b_time < m2.b_time;
    else
        return m1.e_time < m2.e_time;
}

int main()
{
    cout << "Input the number of the meeting:";
    cin >> num;

    for(int i = 0 ; i < num; i++){
        cin >> m[i].b_time >> m[i].e_time;
    }

    sort(m,m+num,cmp);

    for(int i = 0 ; i < num ; i++){
        cout << m[i].b_time << "," << m[i].e_time << endl;
    }

    int now_e_time = m[0].e_time;
    int cnt = 1;
    record.push(m[0]);

    for(int i = 1 ; i < num ; i++)
    {
        if(m[i].b_time > now_e_time)
        {
            now_e_time = m[i].e_time;
            cnt++;
            record.push(m[i]);
        }
    }

    cout << "Max number of the meeting:" << cnt << endl;

    while(!record.empty())
    {
        meeting head = record.front();
        record.pop();
        cout << head.b_time << "," << head.e_time << endl;
    }

    return 0;
}