Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]] Output: 2
Example 2:
Input: intervals = [[7,10],[2,4]] Output: 1
Constraints:
1 <= intervals.length <= 1040 <= starti < endi <= 106Problem Overview: You receive a list of meeting time intervals [start, end]. Multiple meetings may overlap. The task is to compute the minimum number of conference rooms required so every meeting can run without conflict.
Approach 1: Difference Array (Timeline Sweep) (Time: O(n + R), Space: O(R))
This approach treats time as a timeline and tracks how meetings affect room usage. For every meeting interval, increment the value at start and decrement at end. A prefix sum over the timeline reveals how many meetings are active at each time point. The maximum prefix value equals the number of rooms required. This works because each start adds a room requirement and each end releases one. It’s essentially a sweep-line technique implemented with an array. The limitation is the time range R; if timestamps are very large, allocating a full array becomes inefficient.
Conceptually this mirrors a prefix sum accumulation, so understanding prefix sum patterns helps when implementing the running total.
Approach 2: Difference Using Hash Map (Ordered Events) (Time: O(n log n), Space: O(n))
Instead of allocating a full timeline, store only event changes. For every meeting, record +1 at start and -1 at end inside a map. After processing all meetings, sort the time keys and scan them in order while maintaining a running sum of active meetings. The maximum running sum represents the minimum rooms required. This approach avoids large arrays and works efficiently even when timestamps are large or sparse.
This is essentially the classic sweep-line algorithm frequently used in interval problems. It relies on sorting events, a pattern commonly seen in sorting and array interview questions.
Recommended for interviews: The ordered difference map approach is typically expected in interviews because it handles large ranges without wasting memory. Explaining the difference-array idea first shows you understand the underlying timeline concept. Then transitioning to the map-based sweep line demonstrates practical optimization and strong algorithmic reasoning.
We can implement this using a difference array.
First, we find the maximum end time of all the meetings, denoted as m. Then, we create a difference array d of length m + 1. For each meeting, we add to the corresponding positions in the difference array: d[l] = d[l] + 1 for the start time, and d[r] = d[r] - 1 for the end time.
Next, we calculate the prefix sum of the difference array and find the maximum value of the prefix sum, which represents the minimum number of meeting rooms required.
The time complexity is O(n + m) and the space complexity is O(m), where n is the number of meetings and m is the maximum end time.
If the meeting times span a large range, we can use a hash map instead of a difference array.
First, we create a hash map d, where we add to the corresponding positions for each meeting's start time and end time: d[l] = d[l] + 1 for the start time, and d[r] = d[r] - 1 for the end time.
Then, we sort the hash map by its keys, calculate the prefix sum of the hash map, and find the maximum value of the prefix sum, which represents the minimum number of meeting rooms required.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the number of meetings.
| Approach | Complexity |
|---|---|
| Difference Array | — |
| Difference (Hash Map) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Difference Array (Timeline) | O(n + R) | O(R) | When the time range is small and bounded, allowing a direct prefix sum over the timeline |
| Difference with Hash Map (Sweep Line) | O(n log n) | O(n) | General case with large or sparse timestamps where allocating a full timeline is inefficient |
Meeting Rooms II - Leetcode 253 - Python • NeetCode • 229,097 views views
Watch 9 more video solutions →Practice Meeting Rooms II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor