DSA problem
Meeting Rooms II
Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required so that no two overlapping meetings share a room.
The answer is the maximum number of meetings that are simultaneously in progress at any single moment. Equivalently, every distinct room corresponds to one chain of meetings that can be packed end to end without overlap. The challenge is to compute that maximum concurrency efficiently rather than checking every pair of meetings.
A clean way to think about this is to sort by start time and reuse rooms greedily. Process the meetings in start-time order. At each meeting, check the room whose current meeting ends earliest. If that earliest-ending meeting finishes by the time the new meeting starts, the same room can be reused. Otherwise, a fresh room is required. The answer is the size of the room pool at the end (equivalently, the maximum it ever reached).
The data structure that lets you ask "which room ends earliest" in O(log n) is a min-heap keyed on end time. The algorithm therefore runs in O(n log n) time (sort + n heap operations) and O(n) space. A second equally classical approach uses two separate sorted arrays of start and end times — a sweep-line — which delivers the same complexity with even smaller constants.
Examples
intervals = [[0,30],[5,10],[15,20]]2intervals = [[7,10],[2,4]]1intervals = [[1,5],[2,6],[3,7]]3Constraints
- 1 <= intervals.length <= 10^4
- 0 <= start_i < end_i <= 10^6
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.