C++贪心实现会场安排问题

会场安排问题是一道经典的贪心算法问题，其实现过程如下：

1.将所有会议按照结束时间从早到晚排序。

2.选择第一个会议，并将它加入到一个会场中。

3.遍历所有剩余的会议，如果当前会议的开始时间晚于或等于该会场中最后一个会议的结束时间，则将该会议加入到该会场中，否则选择一个新的会场并将该会议加入到该会场中。

4.重复步骤3，直到所有的会议都被分配到了一个会场中。

下面是C++代码实现：

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

struct Meeting {
    int start;
    int end;
};

bool cmp(Meeting a, Meeting b) {
    return a.end < b.end;
}

int main() {
    int n; // 会议数目
    cin >> n;
    Meeting meetings[n];
    for (int i = 0; i < n; i++) {
        cin >> meetings[i].start >> meetings[i].end;
    }
    sort(meetings, meetings + n, cmp); // 按结束时间排序
    int end_time[n]; // 记录每个会场的结束时间
    int cnt = 1; // 记录会场数量
    end_time[0] = meetings[0].end;
    for (int i = 1; i < n; i++) {
        bool flag = false;
        for (int j = 0; j < cnt; j++) {
            if (meetings[i].start >= end_time[j]) {
                end_time[j] = meetings[i].end;
                flag = true;
                break;
            }
        }
        if (!flag) {
            end_time[cnt++] = meetings[i].end;
        }
    }
    cout << cnt;
    return 0;
}

该算法的时间复杂度为 O(nlogn)，其中 n 为会议数目。