253. Meeting Rooms II

MediumGreedyArrayTwo PointersPrefix SumSortingHeap (Priority Queue)

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 index start in the delta array, and decrement the value at index end. 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 the accumulate 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).
```
for start, end in intervals:
    delta[start] += 1
    delta[end] -= 1
```
This creates a timeline indicating when rooms are occupied and vacated.
Calculating the Prefix Sum: We use the accumulate function from the itertools module of Python to create a running sum (also known as a prefix sum) over the delta array. The result is a new array indicating the number of rooms occupied at each time.
```
occupied_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.
```
min_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 Evaluator

Example Walkthrough

Let's consider a small set of meeting intervals to illustrate the solution approach:

Meeting 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 in delta are set to 0.

Updating the delta Array: We iterate through the meeting intervals and update the delta array accordingly.

delta[1] += 1  # Meeting 1 starts, need a room
delta[4] -= 1  # Meeting 1 ends, free a room
delta[2] += 1  # Meeting 2 starts, need a room
delta[5] -= 1  # Meeting 2 ends, free a room
delta[7] += 1  # Meeting 3 starts, need a room
delta[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:

time     1  2  3  4  5  6  7  8  9
delta    +1 +1  0 -1 -1  0 +1  0 -1
occupied  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.

The 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 of 1000010. This step is in O(1) since it does not depend on the number of intervals but on a constant size.
The first for loop that populates the delta array with +1 and -1 for the start and end times of meetings. It runs O(n) times, where n is the number of intervals (meetings).
The use of accumulate which calculates the prefix sum of the delta array. In the worst case, this operation is O(m), where m is the size of the delta array, which is a constant of 1000010.

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 of 1000010. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First Search

Breadth First Search

I don’t know