高效计算电影院最小放映厅数量的算法(C++)

这篇文章介绍一个C++算法，用于计算给定一系列电影放映时间段时，电影院需要的最小放映厅数量。以下是用例场景和代码实现：

场景: 假设你是一位电影院经理，需要安排一整天的电影放映。你有一份清单，上面列出了每部电影的开始和结束时间。你的目标是使用最少的放映厅来安排所有电影，以最大程度地降低成本。

算法: 以下C++代码实现了一个有效的解决方案：c++int minRoom(vector<vector>& intervals) { // 此处设定一个放映厅可以不间断连续放映 vector start, ending; for (unsigned int i = 0; i < intervals.size(); i++) { start.push_back(intervals[i][0]); ending.push_back(intervals[i][1]); } // 将每部电影的开始和结束时间分别放到两个一维数组中 sort(start.begin(), start.end()); // 升序排列开始时间的数组 sort(ending.begin(), ending.end()); // 升序排列结束时间的数组 int room = 0; // 放映厅的数量 int tmp = 0; for (unsigned int i = 0; i < intervals.size(); i++) { if (start[i] < ending[tmp]) room++; // 当前开始时间<前一部结束时间，则需增加放映厅 else tmp++; // 当前开始时间>=前一部结束时间，则放映厅数量不变，此时结束时间改变 // cout << room << ' ' << tmp; } return room;}

算法解释:

分离并排序: 算法首先将所有电影的开始时间和结束时间分别存储在两个数组 start 和 ending 中，并对这两个数组进行升序排序。
贪心策略: 算法使用两个指针 i 和 tmp 分别遍历排序后的 start 和 ending 数组。 * 如果 start[i] < ending[tmp]，这意味着一部新电影在上一部电影结束之前就开始放映了，因此需要一个新的放映厅 (room++)。 * 如果 start[i] >= ending[tmp]，意味着当前电影可以在上一部电影结束后在同一个放映厅放映，因此不需要新的放映厅，只需更新 tmp 指针到下一部结束的电影即可。
返回结果: 遍历完所有电影后，room 变量的值即为所需的最小放映厅数量。

结论:

这个算法提供了一种高效且易于理解的方式来计算电影院所需的最小放映厅数量。通过使用排序和贪心策略，算法能够在 O(n log n) 的时间复杂度内完成计算，其中 n 是电影的数量。这使得算法对于处理大型电影放映时间表非常有效。