Microsoft VO 面试真题解析：最少影厅排片（最少会议室/区间调度）

Assume you run a movie theater that has many auditoriums, and every day you need to schedule movies into those auditoriums.

You want to schedule all movies using the fewest auditoriums.

Each movie has a start time and an end time (inclusive).

Come up with an algorithm to solve this problem using the appropriate data structures and definitions.

Example 1:

[1, 2] [3, 5] [2, 6]

[1, 2] [3, 5]
[2, 6]

2

Example 2:

[1, 2] [5, 8] [3, 8] [2, 6]

[1, 2] [3, 8]
[2, 6]
[5, 8]

3

这道题本质上是“区间重叠最少资源分配”问题：把每部电影看作一个带起止时间的区间，由于结束时间是 inclusive，所以如果一场电影在时间 t 结束，另一场要在同一影厅开始，通常需要从 t 之后才能开始。最优做法是先按开始时间排序，再用最小堆维护当前各影厅已安排电影的最早结束时间；每次取出能最早空出来的影厅，如果它的结束时间早于当前电影开始时间，就复用这个影厅，否则开新影厅。堆中元素数量的最大值或最终值就是所需的最少影厅数。这个思路常见于会议室 / 房间分配类题目，核心数据结构是最小堆，时间复杂度通常为 O(n log n)。