教室分配算法：贪心策略解决活动安排问题

这篇文章将介绍如何使用贪心算法解决经典的教室分配问题，并提供C++代码实现和详细的示例解释。

问题描述：

学校只有一个社团活动教室，同一时间只能有一个社团使用。现在有 n 个社团提交了申请，每个社团希望使用教室的时长是连续的。第 i 个社团的申请是从第 a_i 节课开始到第 b_i 节课结束。由于时间冲突，并非所有申请都能被满足。请问最多有多少个社团能够使用教室？

贪心策略：

为了最大化能够使用教室的社团数量，我们可以采用以下贪心策略：

按照结束时间排序: 将所有申请按照结束时间 b_i 从小到大排序。2. 优先选择结束早的: 从排序后的申请开始，优先选择结束时间早的社团，并将教室分配给它。3. 更新时间限制: 当一个社团获得分配后，更新教室的可用时间，即下一个可分配的时间从当前社团的结束时间开始。

**C++代码实现：**c++#include <bits/stdc++.h>using namespace std;const int N = 1005;int n;

// 定义结构体存储每个申请的信息struct Seg{ int a, b; // a: 开始时间，b: 结束时间} c[N];

// 自定义排序函数，按照结束时间从小到大排序bool cmp(Seg x, Seg y){ return x.b < y.b;}

int main() { scanf('%d', &n); for(int i = 1; i <= n; ++i) scanf('%d%d', &c[i].a, &c[i].b); // 对申请进行排序 sort(c + 1, c + n + 1, cmp); int ans = 0, lim = 0; // ans: 通过申请数量，lim: 当前可分配的最早时间 for(int i = 1; i <= n; ++i){ // 如果当前申请的开始时间晚于等于当前可分配的最早时间 if(c[i].a >= lim){ ++ans; // 通过申请数量加一 lim = c[i].b; // 更新可分配的最早时间为当前申请的结束时间 } } printf('%d ', ans); return 0;}

示例分析:

假设有如下申请:

申请1: 4 - 6申请2: 1 - 3申请3: 2 - 5

按照结束时间排序后: 1-3, 2-5, 4-6。2. 选择结束时间最早的申请 1-3，ans 更新为 1，lim 更新为 3。3. 申请 2-5 的开始时间小于 lim，不符合条件，跳过。4. 申请 4-6 的开始时间大于等于 lim，ans 更新为 2，lim 更新为 6。

最终结果：最多有两个社团能够使用教室。

总结：

本文介绍了如何使用贪心算法解决教室分配问题，并提供了C++代码实现和详细示例分析。希望对你理解和掌握这一经典算法有所帮助。