Meeting Rooms II

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required. A conference room is available if it is not occupied by any meeting at the time of the new meeting.

How it works

1. Initialize a Large Array: delta = [0] * 1000010 creates an array (or list in Python terms) of size 1,000,010, initialized with zeros. This array acts as a map, where the index represents a time point and the value at each index represents the net change in the number of ongoing meetings at that time.
2. Populate the delta Array: For each meeting defined by its start and end times, the code increments the value at the start index by 1 and decrements the value at the end index by 1 in the delta array. This increment and decrement operation effectively marks the beginning and end of a meeting, respectively. The positive value at the start time indicates new meetings starting, and the negative value at the end time indicates meetings ending.
3. Accumulate Changes: The expression accumulate(delta) computes the cumulative sum of the delta array. This step calculates the net number of meetings ongoing at each time point, based on the previously marked start and end times. After accumulation, each value in the delta array represents the total number of meetings ongoing at the corresponding time point.
4. Find the Maximum Value: The maximum value in the accumulated delta array represents the peak number of simultaneous meetings. This peak value is the minimum number of conference rooms needed to accommodate all meetings without any overlap.

Test Cases

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Explanation:
- Room 1 is occupied from 0 to 30.
- Room 2 is occupied from 5 to 10.
- Room 2 is occupied from 15 to 20.

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1
Explanation:
- Room 1 is occupied from 2 to 4.
- Room 1 is occupied from 7 to 10.

Solution

C++ Golang Java Python Typescript

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int n = 1000010;
        vector<int> delta(n);
        for (auto e : intervals) {
            ++delta[e[0]];
            --delta[e[1]];
        }
        for (int i = 0; i < n - 1; ++i) {
            delta[i + 1] += delta[i];
        }
        return *max_element(delta.begin(), delta.end());
    }
};

func minMeetingRooms(intervals [][]int) int {
	n := 1000010
	delta := make([]int, n)
	for _, e := range intervals {
		delta[e[0]]++
		delta[e[1]]--
	}
	for i := 1; i < n; i++ {
		delta[i] += delta[i-1]
	}
	return slices.Max(delta)
}

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = 1000010;
        int[] delta = new int[n];
        for (int[] e : intervals) {
            ++delta[e[0]];
            --delta[e[1]];
        }
        int res = delta[0];
        for (int i = 1; i < n; ++i) {
            delta[i] += delta[i - 1];
            res = Math.max(res, delta[i]);
        }
        return res;
    }
}

class Solution(object):
  def minMeetingRooms(self, intervals):
    """
    :type intervals: List[Interval]
    :rtype: int
    """
    meetings = []
    for i in intervals:
      meetings.append((i.start, 1))
      meetings.append((i.end, 0))
    meetings.sort()
    ans = 0
    count = 0
    for meeting in meetings:
      if meeting[1] == 1:
        count += 1
      else:
        count -= 1
      ans = max(ans, count)
    return ans

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;
}