253. Meeting Rooms II
Problem Description
The problem presents a scenario where we have an array of meeting time intervals, each represented by a pair of numbers [start_i, end_i]
. These pairs indicate when a meeting starts and ends. The goal is to find the minimum number of conference rooms required to accommodate all these meetings without any overlap. In other words, we want to allocate space such that no two meetings occur in the same room simultaneously.
Intuition
The core idea behind the solution is to track the changes in room occupancy over time, which is akin to tracking the number of trains at a station at any given time. We can visualize the timeline from the start of the first meeting to the end of the last meeting, and keep a counter that increments when a meeting starts and decrements when a meeting ends. This approach is similar to the sweep line algorithm, often used in computational geometry to keep track of changes over time or another dimension.
By iterating through all the meetings, we apply these increments/decrements at the respective start and end times. The maximum value reached by this counter at any point in time represents the peak occupancy, thus indicating the minimum number of conference rooms needed. To implement this:
-
We initialize an array
delta
that is large enough to span all potential meeting times. We use a fixed size in this solution, which assumes the meeting times fall within a predefined range (0 to 1000009 in this case). -
Iterate through the intervals list, and for each meeting interval
[start, end]
, increment the value at indexstart
in thedelta
array, and decrement the value at indexend
. This effectively marks the start of a meeting with +1 (indicating a room is now occupied) and the end of a meeting with -1 (a room has been vacated). -
Accumulate the changes in the
delta
array using theaccumulate
function, which applies a running sum over the array elements. The maximum number reached in this accumulated array is our answer, as it represents the highest number of simultaneous meetings, i.e., the minimum number of conference rooms required.
This solution is efficient because it avoids the need to sort the meetings by their start or end times, and it provides a direct way to calculate the running sum of room occupancy over the entire timeline.
Learn more about Greedy, Two Pointers, Prefix Sum, Sorting and Heap (Priority Queue) patterns.
Solution Approach
The solution uses a simple array and the concept of the prefix sum (running sum) to keep track of room occupancy over time—an approach that is both space-efficient and does not require complex data structures.
Here's a step-by-step breakdown of the implementation:
-
Initialization: A large array
delta
is created with all elements initialized to 0. The size of the array is chosen to be large enough to handle all potential meeting times (1 more than the largest possible time to account for the last meeting's end time). In this case,1000010
is used. -
Updating the
delta
Array: For each meeting interval, say[start, end]
, we treat the start time as the point where a new room is needed (increment counter) and the end time as the point where a room is freed (decrement counter).1for start, end in intervals: 2 delta[start] += 1 3 delta[end] -= 1
This creates a timeline indicating when rooms are occupied and vacated.
-
Calculating the Prefix Sum: We use the
accumulate
function from theitertools
module of Python to create a running sum (also known as a prefix sum) over thedelta
array. The result is a new array indicating the number of rooms occupied at each time.1occupied_rooms_over_time = accumulate(delta)
-
Finding the Maximum Occupancy: The peak of the
occupied_rooms_over_time
array represents the maximum number of rooms simultaneously occupied, hence the minimum number of rooms we need.1min_rooms_required = max(occupied_rooms_over_time)
The
max
function is used to find this peak value, which completes our solution.
The beauty of this approach is in its simplicity and efficiency. Instead of worrying about sorting meetings by starts or ends or using complex data structures like priority queues, we leverage the fact that when we are only interested in the max count, the order of increments and decrements on the timeline does not matter. As long as we correctly increment at the start times and decrement at the end times, the accumulate
function ensures we get a correct count at each time point.
In conclusion, this method provides an elegant solution to the problem using basic array manipulation and the concept of prefix sums.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small set of meeting intervals to illustrate the solution approach:
1Meeting intervals: [[1, 4], [2, 5], [7, 9]]
Here we have three meetings. The first meeting starts at time 1 and ends at time 4, the second meeting starts at time 2 and ends at time 5, and the third meeting starts at time 7 and ends at time 9.
Following the solution steps:
-
Initialization: We create an array
delta
of size 1000010, which is a bit overkill for this small example, but let's go with the provided approach. Initially, all elements indelta
are set to 0. -
Updating the
delta
Array: We iterate through the meeting intervals and update thedelta
array accordingly.1delta[1] += 1 # Meeting 1 starts, need a room 2delta[4] -= 1 # Meeting 1 ends, free a room 3delta[2] += 1 # Meeting 2 starts, need a room 4delta[5] -= 1 # Meeting 2 ends, free a room 5delta[7] += 1 # Meeting 3 starts, need a room 6delta[9] -= 1 # Meeting 3 ends, free a room
After the updates, the
delta
array will reflect changes in room occupancy at the start and end times of the meetings. -
Calculating the Prefix Sum: Using an
accumulate
operation (similar to a running sum), we calculate the number of rooms occupied at each point in time. For simplicity, we will perform the cumulation manually:1time 1 2 3 4 5 6 7 8 9 2delta +1 +1 0 -1 -1 0 +1 0 -1 3occupied 1 2 2 1 0 0 1 1 0 (summing up `delta` changes over time)
The maximum number during this running sum is 2, which occurs at times 2 and 3.
-
Finding the Maximum Occupancy: We can see that the highest value in the occupancy timeline is 2, therefore we conclude that at least two conference rooms are needed to accommodate all meetings without overlap.
1The minimum number of conference rooms required is 2.
Solution Implementation
1from typing import List
2from itertools import accumulate
3
4class Solution:
5 def minMeetingRooms(self, intervals: List[List[int]]) -> int:
6 # Initialize a list to keep track of the number of meetings starting or ending at any time
7 # The range is chosen such that it covers all possible meeting times
8 meeting_delta = [0] * 1000010
9
10 # Go through each interval in the provided list of intervals
11 for start, end in intervals:
12 meeting_delta[start] += 1 # Increment for a meeting starting
13 meeting_delta[end] -= 1 # Decrement for a meeting ending
14
15 # The `accumulate` function is used to compute the running total of active meetings at each time
16 # `max` is then used to find the maximum number of concurrent meetings, which is the minimum number of rooms required
17 return max(accumulate(meeting_delta))
18
19# Example usage:
20# sol = Solution()
21# print(sol.minMeetingRooms([[0, 30], [5, 10], [15, 20]])) # Output: 2
22
1class Solution {
2
3 // Function to find the minimum number of meeting rooms required
4 public int minMeetingRooms(int[][] intervals) {
5 // Define the size for time slots (with assumed maximum time as 10^6+10)
6 int n = 1000010;
7 int[] delta = new int[n]; // Array to hold the changes in ongoing meetings
8
9 // Iterate through all intervals
10 for (int[] interval : intervals) {
11 // Increment the start time to indicate a new meeting starts
12 ++delta[interval[0]];
13 // Decrement the end time to indicate a meeting ends
14 --delta[interval[1]];
15 }
16
17 // Initialize res to the first time slot to handle the case if only one meeting
18 int res = delta[0];
19
20 // Traverse over the delta array to find maximum number of ongoing meetings at any time
21 for (int i = 1; i < n; ++i) {
22 // Cumulate the changes to find active meetings at time i
23 delta[i] += delta[i - 1];
24 // Update res if the current time slot has more meetings than previously recorded
25 res = Math.max(res, delta[i]);
26 }
27
28 // Return the maximum value found in delta, which is the minimum number of rooms required
29 return res;
30 }
31}
32
1#include <vector>
2#include <algorithm> // Include necessary headers
3
4class Solution {
5public:
6 // Function to find the minimum number of meeting rooms required
7 int minMeetingRooms(vector<vector<int>>& intervals) {
8 int n = 1000010; // Define the maximum possible time point
9 vector<int> countDelta(n); // Create a vector to keep track of the count changes
10
11 // Iterate over each interval
12 for (auto &interval : intervals) {
13 ++countDelta[interval[0]]; // Increment count at the start time of the meeting
14 --countDelta[interval[1]]; // Decrement count at the end time of the meeting
15 }
16
17 // Prefix sum - accumulate the count changes to find the count at each time
18 for (int i = 0; i < n - 1; ++i) {
19 countDelta[i + 1] += countDelta[i];
20 }
21
22 // Find and return the maximum count at any time, which is the minimum number of rooms required
23 return *max_element(countDelta.begin(), countDelta.end());
24 }
25};
26
1// Import necessary module for max element search
2import { max } from "lodash";
3
4// Function to find the minimum number of meeting rooms required
5function minMeetingRooms(intervals: number[][]): number {
6 const maximumTimePoint: number = 1000010; // Define the maximum possible time point
7 const countChange: number[] = new Array(maximumTimePoint).fill(0); // Create an array to track the count changes, initialized to 0
8
9 // Iterate over each interval
10 intervals.forEach(interval => {
11 countChange[interval[0]]++; // Increment count at the start time of the meeting
12 countChange[interval[1]]--; // Decrement count at the end time of the meeting
13 });
14
15 // Prefix sum calculation - accumulate the count changes to find the count at each time point
16 for (let i = 0; i < maximumTimePoint - 1; ++i) {
17 countChange[i + 1] += countChange[i];
18 }
19
20 // Find and return the maximum count at any time point, which is the minimum number of rooms required
21 return max(countChange);
22}
23
24// Example usage:
25// const intervals: number[][] = [[0, 30], [5, 10], [15, 20]];
26// const numberOfRooms: number = minMeetingRooms(intervals);
27// console.log(numberOfRooms); // Should output the minimum number of meeting rooms required
28
Time and Space Complexity
The provided Python code is meant to determine the minimum number of meeting rooms required for a set of meetings, represented by their start and end times. The code employs a difference array to keep track of the changes in the room occupancy count caused by the start and end of meetings, then uses accumulate
to find the peak occupancy which gives the required number of rooms.
Time Complexity
The time complexity of the code is determined by three steps:
-
Initializing the
delta
list, which has a fixed length of1000010
. This step is inO(1)
since it does not depend on the number of intervals but on a constant size. -
The first
for
loop that populates thedelta
array with+1
and-1
for the start and end times of meetings. It runsO(n)
times, wheren
is the number of intervals (meetings). -
The use of
accumulate
which calculates the prefix sum of thedelta
array. In the worst case, this operation isO(m)
, wherem
is the size of thedelta
array, which is a constant of1000010
.
The final time complexity is dominated by the larger of the two variables, which in this case is the constant time for using accumulate
. Hence, the time complexity is O(m)
, which translates to O(1)
since m
is a constant.
Space Complexity
The space complexity of the code is determined primarily by the delta
array.
-
The
delta
list, which has a fixed length of1000010
. This is a constant space allocation and does not depend on the input size. -
No additional data structures that grow with the size of the input are used.
Therefore, the space complexity is O(1)
due to the constant size of the delta
array.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.