Scan Line Technique: Scheduling Meeting Rooms

In a previous interview, I was asked a very classic and practical algorithm question: the Meeting Room Scheduling Problem.

Similar problems on LeetCode are member-only, so you might not be able to attempt them. However, it's essential to grasp the thought process for such classic algorithm questions.

Let's first discuss the problem, LeetCode #253 "Meeting Rooms II":

You are given several intervals in the form [begin, end], representing the start and end times of various meetings. Your task is to calculate the minimum number of meeting rooms required.

The function signature is as follows:

// Return the number of meeting rooms to be reserved
int minMeetingRooms(int[][] meetings);

// return the number of meeting rooms needed to be booked
int minMeetingRooms(vector<vector<int>>& meetings);

# Return the number of meeting rooms needed to be booked
def minMeetingRooms(meetings: List[List[int]]) -> int:

// return the number of meeting rooms to be booked
func minMeetingRooms(meetings [][]int) int {
}

// return the number of meeting rooms to be scheduled
var minMeetingRooms = function(meetings) {
};

For example, given the input meetings = [[0,30],[5,10],[15,20]], the algorithm should return 2 because the last two meetings overlap with the first one. At least two meeting rooms are needed to hold all meetings without conflicts.

If meeting times overlap, additional rooms are required. To find the minimum number of rooms needed, you need to calculate the maximum number of meetings happening at the same time.

In other words, if you consider the start time of each meeting as a segment interval, the problem is asking you to find the maximum number of overlapping intervals, that's all.

We have previously studied interval-related algorithms. If you remember the Difference Array Technique, you might think of using that technique to solve this problem first.

This problem is essentially saying: given an array initially filled with zeros, and several intervals, you need to increment each element within these intervals by 1. The question is, what is the maximum value in the array at the end? This is a classic application scenario for the difference array, right? You can directly use the Difference class provided in the previous article to solve this problem.

However, there is an issue with the difference array technique: you must construct the initial array of zeros. Since we use array indices to represent time, the length of this array depends on the maximum value of the time intervals.

For example, with the input meetings = [[0,30],[5,10],[15,20]], you need to construct an array of length 30. But if the input is meetings = [[0,30],[5,10],[10^8,10^9]], you would need to construct an array of length 10^9, which is clearly problematic. However, the data scale given in this problem limits the maximum time value to 10^6, which is not extremely large, so the difference array method should work.

But this article will teach you another technique for handling intervals, which does not require constructing such a large array and can cleverly solve this problem.

Topic Extension

We have written many articles about interval scheduling before. Let's review the thought process for these types of problems:

First Scenario: Suppose there is only one meeting room and several meetings. How do you schedule as many meetings as possible in this room?

This problem requires sorting the meetings (intervals) by their end times (right endpoints) and then processing them. See the previous article Greedy Algorithm for Time Management for details.

Second Scenario: Given several short video clips and one longer video clip, select as few short clips as possible to splice together and form the longer clip.

This problem requires sorting the video clips (intervals) by their start times (left endpoints) and then processing them. See the previous article Editing Videos with a Greedy Algorithm for details.

Third Scenario: Given several intervals, some of which may be completely covered by others, delete these covered intervals.

This problem requires sorting the intervals by their left endpoints to find and delete the fully covered intervals. See the previous article Deleting Covered Intervals for details.

Fourth Scenario: Given several intervals, merge all intervals that overlap.

This problem requires sorting the intervals by their left endpoints to easily identify overlapping intervals. See the previous article Merging Overlapping Intervals for details.

Fifth Scenario: Two departments have booked the same meeting room for different time periods. Calculate the conflicting time slots for the meeting room.

This problem involves finding the intersection of two sets of interval lists. You need to sort these intervals by their left endpoints. See the previous article Interval Intersection Problem for details.

Sixth Scenario: Suppose there is only one meeting room and several meetings. How do you schedule the meetings to minimize the room's idle time?

This problem requires some thinking. Essentially, it's a variation of the 0-1 knapsack problem:

Consider the meeting room as a knapsack and each meeting as an item. The value of an item is the duration of the meeting. How do you choose items (meetings) to maximize the value (usage time) of the knapsack (meeting room)?

Here, the constraint is not a maximum weight but that items (meetings) must not conflict. Sort the meetings by their end times and refer to the previous article 0-1 Knapsack Problem Explained along with TreeMap to solve this.

LeetCode problem 1235 "Plan Work Schedules" is a similar question. I provided a detailed solution in my plugin's approach. You can install my Chrome Plugin to check it out. I won't elaborate further here.

Seventh Scenario: The scenario this article focuses on—given several meetings, minimize the number of meeting rooms required.

With these examples in mind, let's see how to solve today's problem.