Intervals · LC #253
Meeting Rooms II
Find the minimum number of conference rooms required by tracking peak simultaneous meetings - solved optimally via separate sorted starts/ends arrays or a min-heap of end times.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Return the minimum number of conference rooms required to hold all meetings.
Sample I/O
Input: [[0,30],[5,10],[15,20]] Output: 2 Input: [[7,10],[2,4]] Output: 1
Intuition
How to Think About It
Intuition
The answer equals the maximum number of meetings overlapping at any single point in time. By separately sorting starts and ends, we can simulate a timeline sweep: each new start that arrives before the earliest pending end requires an additional room.
Core Concept
Separate starts and ends arrays, both sorted. Use two pointers: for each start, if it's < the current earliest end, we need a new room (rooms++); otherwise a room is freed (endPtr++). Final value of rooms is peak concurrency.
When to use
Resource allocation: minimum servers, minimum CPU cores, minimum parallel workers needed to handle a task stream.
When NOT to use
When you need to know which meetings share each room (use a min-heap of [endTime, roomId] instead); when intervals are 2D.
Key Insights
What to Know Cold
- Two-pointer on sorted starts/ends is O(n log n) time, O(n) space, and simpler than a heap.
- Heap alternative: min-heap of end times; pop when top <= new start (room freed), push new end.
- Peak rooms = max simultaneous events = sweep-line max at any point.
- Sorting starts and ends INDEPENDENTLY is the key - pairing is irrelevant.
- endPtr never decreases - total work is O(n) after O(n log n) sort.
1 example
Worked Examples
Allocate conference rooms
Meetings [[0,30],[5,10],[15,20]] - minimum rooms?
Sort starts and ends separately, two-pointer sweep.
Output: 2
Classic resource-allocation pattern appears in cloud-instance provisioning, thread-pool sizing, and bandwidth scheduling.