Sweaty Imposter

Meeting Rooms II

MediumMerge IntervalsNeetCode 150MidOpen on LeetCodeUpdated

You're given an array intervals where intervals[i] = [start, end] is a meeting that needs a room from start until end. Return the minimum number of conference rooms needed so every meeting has a room for its whole duration. A meeting that ends at time t frees its room for one that starts at t, so [1,5] and [5,8] can share a room. The meetings are given in no particular order.

Examples

intervals = [[0,30],[5,10],[15,20]] returns 2

[0,30][5,10][15,20]051015202530
The highlighted meetings never overlap, so they share the second room.

[0,30] runs the whole time, and [5,10] starts while it's running, so a second room is needed. [15,20] also overlaps [0,30], but [5,10] has ended by then, so it reuses that room. No more than two meetings ever run at once.

intervals = [[7,10],[2,4]] returns 1

[2,4] ends before [7,10] starts, so one room can host both, one after the other.

intervals = [[9,10],[4,9],[4,17]] returns 2

[9,10][4,9][4,17]4681012141618
[4,9] ends at 9, so [9,10] reuses its room.

[4,9] and [4,17] start together, so two rooms are busy from time 4. [9,10] starts exactly when [4,9] ends, so it takes over that room instead of needing a third.

Constraints

  • 1 <= intervals.length <= 10^4

Hints

Hint 1

When a meeting starts, you only need to know the earliest one that has already ended, can you query that quickly?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Sort meetings by start and keep a min-heap of end times, one per room in use. For each meeting, if the earliest end is <= its start, that room is free, so pop it. Then push this meeting's end. The heap only grows when every room is busy, so its final size is the number of rooms needed, which equals the most meetings running at once.

Time

O(n log n)

Space

O(n)

Pitfall

A meeting ending at 10 frees its room for one starting at 10, so reuse a room when end <= start, not end < start. Sort by start first: unsorted, [[10,20],[0,5],[5,10]] asks for 2 rooms when 1 is enough.

Solutions

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int[] iv : intervals) {
            if (!heap.isEmpty() && heap.peek() <= iv[0]) heap.poll();
            heap.offer(iv[1]);
        }
        return heap.size();
    }
}
Drill This