Microsoft VO Interview Question: Minimum Number of Auditoriums to Schedule Movies

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

This is a classic interval-partitioning problem: each movie is an interval, and because the end time is inclusive, two movies can share an auditorium only if the next one starts after the previous one truly finishes. A standard solution is to sort movies by start time and use a min-heap to track the earliest ending auditorium currently in use. For each movie, reuse the auditorium with the smallest end time if it is available; otherwise, allocate a new auditorium. The heap size gives the minimum number of auditoriums required, and the approach runs in O(n log n) time.