Scan Line Technique: Scheduling Meeting Rooms

During a previous interview, I was asked a very classic and practical algorithm problem: the Meeting Room Scheduling problem.

A similar problem on LeetCode is a subscription-only question, which you might not be able to access. However, understanding the approach to such classic algorithm problems is still essential.

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

You are given several intervals in the form [begin, end], representing the start and end times of several meetings. Please 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.

Problem Extensions

We have previously written many articles related to interval scheduling. Here is a summary of the thought process for these types of problems:

First Scenario: Suppose there is only one conference room and several meetings. How can you schedule the maximum number of meetings in this room?

This problem requires sorting these meetings (intervals) by their end time (right endpoint) and then processing them. For details, see the previous article Greedy Algorithm for Time Management.

Second Scenario: Given several short video clips and one longer video clip, select the fewest number of short clips to splice together the longer clip.

This problem requires sorting these video clips (intervals) by their start time (left endpoint) and then processing them. For details, see the previous article Video Clip Greedy Algorithm.

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

This problem requires sorting these intervals by the left endpoint, then finding and deleting the completely covered intervals. For details, see the previous article Deleting Covered Intervals.

Fourth Scenario: Given several intervals, merge all overlapping intervals.

This problem requires sorting these intervals by the left endpoint to easily find overlapping intervals. For details, see the previous article Merging Overlapping Intervals.

Fifth Scenario: Two departments simultaneously reserve several time slots in the same conference room. Calculate the conflicting time slots.

This problem involves two lists of intervals. Find the intersection of these interval lists, requiring sorting by the left endpoint. For details, see the previous article Interval Intersection Problem.

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

This problem is a variation of the 0-1 knapsack problem:

The conference room can be seen as a knapsack, each meeting as an item, and the item's value as the meeting's duration. How do you choose items (meetings) to maximize the knapsack's value (room's usage time)?

The constraint here is not a maximum weight but that the items (meetings) cannot overlap. Sort meetings by their end time, then refer to the previous article 0-1 Knapsack Problem Explained and TreeMap to solve it.

LeetCode Problem 1235, Maximum Profit in Job Scheduling, is a similar problem. I provide a detailed solution in my plugin, which you can view by installing my Chrome Plugin. I won't elaborate here.

Seventh Scenario: The scenario this article intends to discuss, given several meetings, minimize the number of conference rooms required.

Now that we have listed so many examples, let's see how to solve today's problem.