Watch 10 video solutions for Meeting Rooms II, a medium level problem involving Array, Two Pointers, Greedy. This walkthrough by NeetCode has 174,315 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |