Welcome to Subscribe On Youtube
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^{4}
0 <= start_{i} < end_{i} <= 10^{6}
Solutions
The solution employs a technique using a concept similar to the line sweep
algorithm and partial sum accumulation.
How it Works:

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.  Populate the
delta
Array: For each meeting defined by its
start
andend
times, the code increments the value at thestart
index by 1 and decrements the value at theend
index by 1 in thedelta
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 theend
time indicates meetings ending.
 For each meeting defined by its
 Accumulate Changes:
 The expression
accumulate(delta)
computes the cumulative sum of thedelta
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.
 The expression
 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.
 The maximum value in the accumulated
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 fixedsize 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[i1] } 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 } }