253. Meeting Rooms II 🔒

Description

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required.

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⁴
0 <= start_i < end_i <= 10⁶

Solutions

Solution 1: Difference Array

We can implement this using a difference array.

First, we find the maximum end time of all the meetings, denoted as \(m\). Then, we create a difference array \(d\) of length \(m + 1\). For each meeting, we add to the corresponding positions in the difference array: \(d[l] = d[l] + 1\) for the start time, and \(d[r] = d[r] - 1\) for the end time.

Next, we calculate the prefix sum of the difference array and find the maximum value of the prefix sum, which represents the minimum number of meeting rooms required.

The time complexity is \(O(n + m)\) and the space complexity is \(O(m)\), where \(n\) is the number of meetings and \(m\) is the maximum end time.

Python3JavaC++GoTypeScriptRust

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        m = max(e[1] for e in intervals)
        d = [0] * (m + 1)
        for l, r in intervals:
            d[l] += 1
            d[r] -= 1
        ans = s = 0
        for v in d:
            s += v
            ans = max(ans, s)
        return ans

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int m = 0;
        for (var e : intervals) {
            m = Math.max(m, e[1]);
        }
        int[] d = new int[m + 1];
        for (var e : intervals) {
            ++d[e[0]];
            --d[e[1]];
        }
        int ans = 0, s = 0;
        for (int v : d) {
            s += v;
            ans = Math.max(ans, s);
        }
        return ans;
    }
}

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int m = 0;
        for (const auto& e : intervals) {
            m = max(m, e[1]);
        }
        vector<int> d(m + 1);
        for (const auto& e : intervals) {
            d[e[0]]++;
            d[e[1]]--;
        }
        int ans = 0, s = 0;
        for (int v : d) {
            s += v;
            ans = max(ans, s);
        }
        return ans;
    }
};

func minMeetingRooms(intervals [][]int) (ans int) {
    m := 0
    for _, e := range intervals {
        m = max(m, e[1])
    }

    d := make([]int, m+1)
    for _, e := range intervals {
        d[e[0]]++
        d[e[1]]--
    }

    s := 0
    for _, v := range d {
        s += v
        ans = max(ans, s)
    }
    return
}

function minMeetingRooms(intervals: number[][]): number {
    const m = Math.max(...intervals.map(([_, r]) => r));
    const d: number[] = Array(m + 1).fill(0);
    for (const [l, r] of intervals) {
        d[l]++;
        d[r]--;
    }
    let [ans, s] = [0, 0];
    for (const v of d) {
        s += v;
        ans = Math.max(ans, s);
    }
    return ans;
}

impl Solution {
    pub fn min_meeting_rooms(intervals: Vec<Vec<i32>>) -> i32 {
        let mut m = 0;
        for e in &intervals {
            m = m.max(e[1]);
        }

        let mut d = vec![0; (m + 1) as usize];
        for e in intervals {
            d[e[0] as usize] += 1;
            d[e[1] as usize] -= 1;
        }

        let mut ans = 0;
        let mut s = 0;
        for v in d {
            s += v;
            ans = ans.max(s);
        }

        ans
    }
}

Solution 2: Difference (Hash Map)

If the meeting times span a large range, we can use a hash map instead of a difference array.

First, we create a hash map \(d\), where we add to the corresponding positions for each meeting's start time and end time: \(d[l] = d[l] + 1\) for the start time, and \(d[r] = d[r] - 1\) for the end time.

Then, we sort the hash map by its keys, calculate the prefix sum of the hash map, and find the maximum value of the prefix sum, which represents the minimum number of meeting rooms required.

The time complexity is \(O(n \times \log n)\) and the space complexity is \(O(n)\), where \(n\) is the number of meetings.