Sweep Line — Meeting Rooms II

↗ LeetCode: Meeting Rooms II · Medium · pattern chapter →

Asked atMetaAmazonGoogleMicrosoftBloomberg

Given meeting intervals [[start, end)], return the minimum number of rooms required.

Example 1 — [[0,30],[5,10],[15,20]] → 2Example 2 — [[7,10],[2,4]] → 1

Constraints — 1 ≤ n ≤ 10⁴; 0 ≤ start < end ≤ 10⁶.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Brute force (per-minute counter)

Intuition. For each minute in [0..max_end), count active meetings; take the max.

int minMeetingRoomsBrute(int[][] meetings) {
    int mx = 0;
    for (int[] m : meetings) mx = Math.max(mx, m[1]);
    int rooms = 0;
    for (int t = 0; t < mx; t++) {
        int active = 0;
        for (int[] m : meetings) if (m[0] <= t && t < m[1]) active++;
        rooms = Math.max(rooms, active);
    }
    return rooms;
}

Complexity — Time O(n · max_end); Space O(1). Fails when times are large.

---

Approach 2 — Sort ends + heap of end times

Insight from brute. We only care about times where the count changes. Sort by start. A min-heap of end times of running meetings: when starting a new one, if the earliest end ≤ new start, reuse that room (replace); otherwise add a new room.

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

Execution Trace

Heap approach — meetings=[[0,30],[5,10],[15,20]]

Step 1 / 4first meeting → room 1 ends at 30

Complexity — Time O(n log n); Space O(n).

---

Approach 3 — Two-array sweep (chronological events)

Insight from heap. Sort starts and ends separately. Walk both with two pointers. A start bumps the counter; a start-time ≥ the smallest end means that end has already fired first — a room freed. Track running max.

int minMeetingRooms(int[][] meetings) {
    int n = meetings.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = meetings[i][0]; ends[i] = meetings[i][1]; }
    Arrays.sort(starts); Arrays.sort(ends);
    int rooms = 0, peak = 0, e = 0;
    for (int s = 0; s < n; s++) {
        if (starts[s] < ends[e]) { rooms++; peak = Math.max(peak, rooms); }
        else                     { e++; }
    }
    return peak;
}

Complexity — Time O(n log n); Space O(n). No heap, tight and easy to verify.

---

Try it yourself

Complexity summary

Approach	Time	Space
Per-minute counter	O(n · max_end)	O(1)
Heap of end times	O(n log n)	O(n)
Two-array sweep	O(n log n)	O(n)

When to use which

• Cold interview → walk brute → heap → two-array. Show the "we only care about events" reframing.
• Tie at start == end → decide with the interviewer: touching = one room or two?

✨AI Study CompanionBeta

Related problems (same ladder applies)

• Car Pooling — same shape with capacity checks
• The Skyline Problem — sweep + heap for max heights over intervals
• My Calendar II — sweep with 2-limit constraint
• Employee Free Time — flatten schedules, then find gaps

Was this page helpful?