Meeting Rooms II

NeetCode: Meeting Rooms II · LeetCode: 253. Meeting Rooms II · Difficulty: Medium

You are given an array of meeting time intervals [start, end] with start < end. Return the minimum number of rooms needed so that no two overlapping meetings share a room. A meeting ending at time t frees its room for one starting at t.

Example

Text

Input:  intervals = [[0,40],[5,10],[15,20]]    Output: 2
Input:  intervals = [[4,9]]                    Output: 1

Brute force: count overlaps at each start time

The number of rooms needed equals the largest number of meetings running at the same moment, and that maximum is always reached at some meeting's start time. So for each start time, count how many meetings are running (start <= t < end) and take the maximum.

Java

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int best = 0;
        for (int[] m : intervals) {
            int t = m[0];
            int running = 0;
            for (int[] other : intervals) {
                if (other[0] <= t && t < other[1]) {
                    running++;
                }
            }
            best = Math.max(best, running);
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minMeetingRooms(new int[][] {{0, 40}, {5, 10}, {15, 20}}));
        System.out.println(solution.minMeetingRooms(new int[][] {{4, 9}}));
        System.out.println(solution.minMeetingRooms(new int[][] {{1, 5}, {5, 8}}));
        System.out.println(solution.minMeetingRooms(new int[][] {}));
    }
}

Output

Time: O(n^2). Space: O(1).

Optimal: sorted starts and ends with two pointers

Separate the start times and end times and sort each array on its own; only the number of meetings in progress matters, not which end belongs to which start. Sweep through the starts in order. For each start, if the earliest unfinished end is <= this start, some meeting has finished, so reuse its room (advance the end pointer). Otherwise a new room is needed. The number of rooms opened is the answer.

For [[0,40],[5,10],[15,20]]: starts [0,5,15], ends [10,20,40]. Start 0: no end yet, rooms = 1. Start 5 < 10: rooms = 2. Start 15 >= 10: reuse. Answer 2.

Java

import java.util.Arrays;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] starts = new int[n];
        int[] 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;
        int endIdx = 0;
        for (int s : starts) {
            if (s >= ends[endIdx]) {
                endIdx++; // a meeting has finished: reuse its room
            } else {
                rooms++;
            }
        }
        return rooms;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minMeetingRooms(new int[][] {{0, 40}, {5, 10}, {15, 20}}));
        System.out.println(solution.minMeetingRooms(new int[][] {{4, 9}}));
        System.out.println(solution.minMeetingRooms(new int[][] {{1, 5}, {5, 8}}));
        System.out.println(solution.minMeetingRooms(new int[][] {}));
    }
}

Output

Time: O(n log n). Space: O(n).

endIdx can never run past the end: at the i-th start at most i ends are <= it, and there are n ends, so the index stays below n whenever it is read. The empty input skips the loop entirely. Arrays.sort on a primitive int[] sorts in ascending order. A min-heap of end times (poll when the earliest end <= the new start, add the new end, answer = the heap's peak size) reaches the same O(n log n).