Merge Intervals from Data Stream
Problem
You receive meeting intervals as a stream of `[start, end)` pairs. After each insertion, return the minimum number of conference rooms required so that no meetings overlap.
Implement:
- `MeetingRooms()` constructor
- `int addMeeting(int start, int end)` — adds an interval and returns current room count needed
Example: after adding [0,30), [5,10), [15,20) the answer is 2.
Common follow-ups
- Can you support deletion of meetings?
- How would you handle intervals arriving out of order?
Step-by-step study guide
Step 1: Clarify the problem
Each call adds one meeting `[start, end)` — half-open interval (end is exclusive). Return the number of rooms needed **right now** so no meetings overlap. Meetings can overlap partially.
Ask: Can start >= end? Are times integers? Do meetings arrive in sorted order?
Step 2: Trace the example
Add [0, 30): one room active → return 1.
Add [5, 10): overlaps [0,30) → two concurrent meetings → return 2.
Add [15, 20): still overlaps [0,30) but [5,10) has ended → still two active ([0,30) and [15,20)) → return 2.
Step 3: Brute force
Store all intervals. After each add, sort by start and sweep: for each meeting count overlaps with all others. O(n²) per insertion — acceptable only for tiny n.
Step 4: Identify the pattern
This is the **Meeting Rooms II** variant: minimum rooms = maximum concurrent meetings.
Classic approach: min-heap of **end times** of meetings still in progress. When a new meeting starts, free any room whose previous meeting ended (heap min <= start).
Step 5: Design with a min-heap
Maintain `ends` — min-heap of end times for active meetings.
On `addMeeting(start, end)`:
- While heap is not empty and smallest end <= start, pop (room freed).
- Push `end` (meeting occupies a room).
- Return heap size.
Why it works: heap size = meetings running simultaneously after reusing freed rooms.
Step 6: Implement and test
Edge cases: first meeting; back-to-back meetings where end == next start (should reuse room); completely nested intervals; identical intervals.
Example: [0,10), [10,20) → after second add, first ends when second starts → heap size 1.
Step 7: Complexity and follow-ups
- Time: O(log n) per insertion (heap push/pop)
- Space: O(n) for active meetings
Deletion: store meeting id → end time, lazy-remove from heap or use balanced BST.
Out-of-order arrivals: heap approach still works — no need for sorted input.
Solution
# Solution locked # Sign in to unlock expert solutions # with multi-language code and analysis
Sign in to unlock
Create a free account to preview problems. Subscribe for full access to our curated bank — expert tutorials, follow-ups, and practice tools you won't find on public sites.