Scan Line Technique: Scheduling Meeting Rooms
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 253. Meeting Rooms II🔒 | 🟠 |
In a previous interview, I was asked a classic and practical algorithm problem: the Meeting Room Scheduling problem.
There is a similar problem on LeetCode, but it is a paid problem. Even if you cannot try it online, you should still learn the idea behind this kind of classic algorithm problem.
Here is the problem: LeetCode 253 Meeting Rooms II:
You are given several intervals in the form [begin, end], which represent the start and end times of some meetings. Please calculate the minimum number of meeting rooms required.
The function signature is:
// 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, if the input is meetings = [[0,30],[5,10],[15,20]], the algorithm should return 2. This is because the last two meetings overlap with the first one, so you need at least two meeting rooms to hold all the meetings smoothly.
If meeting times overlap, you need extra rooms. To find the minimum number of rooms, you need to calculate the maximum number of meetings happening at the same time.
In other words, if you see each meeting as an interval, the problem is asking for the maximum number of overlapping intervals.
We have learned algorithms related to intervals before. If you remember the difference array technique, you might think of using it here.
This problem is like: you have an array filled with 0, and you get several intervals. For each interval, you add 1 to every element in that interval. At the end, you are asked for the maximum value in the array. This is a classic use case for the difference array. You can directly use the Difference class introduced earlier to solve it.
However, there is a problem with the difference array method: you have to build that initial array filled with 0. Since the array index represents time, the length of the array depends on the maximum time value.
For example, if the input is meetings = [[0,30],[5,10],[15,20]], you need to build an array of length 30. But if the input is meetings = [[0,30],[5,10],[10^8,10^9]], you would need an array of length 10^9, which is clearly a problem. In this problem, the time range is up to 10^6, which is not very big, so the difference array method can still work.
But in this article, I will teach you another interval processing trick. You do not need to build a large array, and you can still solve the problem cleverly.
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.