会场安排问题贪心算法

会场安排问题贪心算法的核心思想是选择局部最优解，即在最少的会场中安排足够多的活动。算法的具体步骤如下：

1. 将待安排的活动按照结束时间的先后顺序进行排序。
2. 初始化一个可安排的空闲时间段为0，表示当前没有任何会场被安排活动。
3. 遍历排好序的活动列表，对于每个活动：
- 如果当前活动的开始时间大于当前可安排的空闲时间段的结束时间，并且该活动未被安排过，则将该活动加入该会场，并更新当前可安排的空闲时间段为该活动的结束时间。
- 如果当前活动的开始时间小于等于当前可安排的空闲时间段的结束时间，表示该活动和已安排的活动有冲突，需要安排到下一个会场。
4. 遍历一次后，使用的会场数即为最少会场数。

下面是一个案例代码的示例：

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

struct Activity {
    int start, end;
    bool scheduled;
};

int arrange(int k, Activity *activities) {
    int count = k, room_avail = 0, room_num = 0;
    while (count > 0) {
        for (int i = 0; i < k; i++) {
            if (activities[i].start > room_avail && !activities[i].scheduled) {
                room_avail = activities[i].end;
                activities[i].scheduled = true;
                count--;
            }
        }
        room_avail = 0;
        room_num++;
    }
    return room_num;
}

int main() {
    int k, room_num;
    cin >> k;
    Activity activities[k];
    for (int i = 0; i < k; i++) {
        cin >> activities[i].start >> activities[i].end;
        activities[i].scheduled = false;
    }
    room_num = arrange(k, activities);
    cout << room_num << endl;
    return 0;
}

这个算法会将活动按照结束时间的先后顺序进行排序，然后遍历每个活动，选择合适的会场进行安排，直到所有的活动都被安排完毕。最终输出的结果是使用最少会场数的时间表。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [会场安排问题（贪心算法）](https://blog.csdn.net/weixin_43553142/article/details/103571130)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]