Meeting Rooms II

Medium Intervals Line Sweep Original on NeetCode

Meeting Rooms II is a medium intervals problem solved with the line sweep pattern. The best approach, line sweep (two sorted arrays), runs in O(n log n) time and O(n) space. Below are 2 approaches in Java, from min-heap of end times up.

Problem

Given meeting times as [start, end) intervals, return the minimum number of conference rooms needed to hold all of them.

Examples

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 <= 10^4
Meetings are [start, end); a room freed at 10 can host a meeting starting at 10.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Min-heap of end times	`O(n log n)`	`O(n)`
Line sweep (two sorted arrays)	`O(n log n)`	`O(n)`

1Min-heap of end times

TimeO(n log n)

SpaceO(n)

Sort by start. Keep a min-heap of the end times of meetings in progress. Before placing a meeting, free the room that ends earliest if it has ended by now. The heap's largest size is the answer.

Sort by start.
For each meeting: if heap.peek() <= start, poll. Offer end.
Return the heap size (it only grows when a new room is needed).

Java

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

2Line sweep (two sorted arrays)

TimeO(n log n)

SpaceO(n)

Sort all start times and all end times separately. Walk the starts; each start needs a room unless some meeting has already ended by then, in which case that room is reused. The running count of rooms in use peaks at the answer.

starts[], ends[] sorted.
For each start: if start >= ends[e], e++ (reuse); else rooms++.

Java

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] starts = new int[n], ends = new int[n];
        for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int rooms = 0, e = 0;
        for (int s : starts) {
            if (s >= ends[e]) e++;
            else rooms++;
        }
        return rooms;
    }
}

Edge cases to test

Back-to-back meetings
All meetings at the same time

Hints

Hint 1

The answer is the maximum number of meetings running at the same moment. Sweep through all start and end times in order.

FAQ

What is the best time complexity for Meeting Rooms II?

Line sweep (two sorted arrays) runs in O(n log n) time and O(n) extra space.

Which pattern does Meeting Rooms II use?

It is a intervals problem that uses the line sweep pattern. Other problems with the same pattern: Car Pooling.

Is there a brute force solution for Meeting Rooms II?

Yes. Min-heap of end times takes O(n log n) time and O(n) space. Sort by start.

Which edge cases should I test for Meeting Rooms II?

Back-to-back meetings; All meetings at the same time.