C++贪心算法解决会场调度问题

问题描述

给定一系列活动的时间段，目标是合理安排这些活动，使得所使用的会场数量最少。每个活动都有一个开始时间和结束时间，且在同一会场内，任何两个活动的时间段不能重叠。

题目分析

此问题类似于经典的活动选择问题，但重点在于最小化会场的使用数量。如果所有活动的时间段都不冲突，则只需一个会场即可。对于存在时间冲突的活动，需要额外的会场来保证每个活动都能顺利进行。解决这一问题的一种有效方法是使用贪心算法，具体步骤如下：

• 首先，按照活动的结束时间对所有活动进行排序。
• 然后，选择最早结束的活动，并为其分配一个会场。
• 接下来，继续选择下一个与已选活动不冲突的活动，并尝试将其安排在同一个会场中。
• 重复上述过程，直到所有活动都被妥善安排。

这种方法确保了每次选择的活动都是当前最优的选择，从而逐步构建出全局最优解。

代码实现

#include 
#include 
#include 
using namespace std;

struct Activity {
    int start, finish;
};

bool compare(Activity s1, Activity s2) {
    return (s1.finish }

void minRooms(vector& activities) {
    sort(activities.begin(), activities.end(), compare);
    vector rooms;
    for (auto act : activities) {
        bool assigned = false;
        for (int i = 0; i             if (rooms[i] <= act.start) {
                rooms[i] = act.finish;
                assigned = true;
                break;
            }
        }
        if (!assigned) {
            rooms.push_back(act.finish);
        }
    }
    cout <<"Minimum number of rooms required: " <}

int main() {
    int n;
    cin >> n;
    vector activities(n);
    for (int i = 0; i         cin >> activities[i].start >> activities[i].finish;
    }
    minRooms(activities);
    return 0;
}

总结

该算法的时间复杂度为O(n log n)，主要由排序操作决定；空间复杂度为O(n)，用于存储活动信息和会场分配情况。通过贪心策略，我们可以高效地解决会场调度问题，确保资源的最优利用。