Welcome to Subscribe On Youtube

253. Meeting Rooms II

Description

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], 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 <= 104
  • 0 <= starti < endi <= 106

Solutions

The solution employs a technique using a concept similar to the line sweep algorithm and partial sum accumulation.

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.

Example:

Given intervals = [[1,5],[9,11],[3,10],[2,7]], the solution works as follows:

  • Initially, delta is all zeros.
  • After processing the intervals, delta at relevant indices would be updated as follows:
    • delta[1] becomes 1 (meeting starting at time 1),
    • delta[5] becomes -1 (meeting ending at time 5),
    • and so on for other intervals.
  • The accumulation step then calculates the running total of meetings at each time, effectively tracking how many meetings are ongoing at any given time.
  • The maximum value in this accumulated array gives the highest number of simultaneous meetings, which in this case would require an equal number of meeting rooms.

Efficiency:

This solution is efficient because it condenses the problem into a single pass through a fixed-size array (assuming meeting times are bounded by the array’s size) and a single pass to accumulate changes, both of which are linear operations. The overall time complexity is (O(N + T)), where (N) is the number of intervals and (T) is the fixed size of the delta array, making it highly efficient for the given problem constraints.

  • 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 {
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());
    }
};

  • '''
data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]

list(accumulate(data, operator.mul))     # running product
[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]

list(accumulate(data, max))              # running maximum
[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]


>>> from itertools import accumulate
>>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]
>>> accumulate(data)
<itertools.accumulate object at 0x10fd78440>
>>> list(accumulate(data))
[3, 7, 13, 15, 16, 25, 25, 32, 37, 45]
>>> max(accumulate(data))
45

https://docs.python.org/3/library/itertools.html#itertools.accumulate


# Amortize a 5% loan of 1000 with 4 annual payments of 90
cashflows = [1000, -90, -90, -90, -90]
list(accumulate(cashflows, lambda bal, pmt: bal*1.05 + pmt))
[1000, 960.0, 918.0, 873.9000000000001, 827.5950000000001]
'''
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        delta = [0] * 1000010
        for start, end in intervals:
            delta[start] += 1
            delta[end] -= 1
        return max(accumulate(delta))
        # why not delta.sort()?
        # because accumulate() will go by order from index 0 to index final
        # just like, from sortedcontainers import SortedDict

############

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



  • 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)
}

  • use std::{ collections::BinaryHeap, cmp::Reverse };

impl Solution {
    #[allow(dead_code)]
    pub fn min_meeting_rooms(intervals: Vec<Vec<i32>>) -> i32 {
        // The min heap that stores the earliest ending time among all meeting rooms
        let mut pq = BinaryHeap::new();
        let mut intervals = intervals;
        let n = intervals.len();

        // Let's first sort the intervals vector
        intervals.sort_by(|lhs, rhs| { lhs[0].cmp(&rhs[0]) });

        // Push the first end time to the heap
        pq.push(Reverse(intervals[0][1]));

        // Traverse the intervals vector
        for i in 1..n {
            // Get the current top element from the heap
            if let Some(Reverse(end_time)) = pq.pop() {
                if end_time <= intervals[i][0] {
                    // If the end time is early than the current begin time
                    let new_end_time = intervals[i][1];
                    pq.push(Reverse(new_end_time));
                } else {
                    // Otherwise, push the end time back and we also need a new room
                    pq.push(Reverse(end_time));
                    pq.push(Reverse(intervals[i][1]));
                }
            }
        }

        pq.len() as i32
    }
}

All Problems

All Solutions