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 <= 1040 <= starti < endi <= 106
Solutions
Solution 1
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] * 1000010creates 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
deltaArray:- For each meeting defined by its
startandendtimes, the code increments the value at thestartindex by 1 and decrements the value at theendindex by 1 in thedeltaarray. - This increment and decrement operation effectively marks the beginning and end of a meeting, respectively. The positive value at the
starttime indicates new meetings starting, and the negative value at theendtime indicates meetings ending.
- For each meeting defined by its
- Accumulate Changes:
- The expression
accumulate(delta)computes the cumulative sum of thedeltaarray. 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
deltaarray represents the total number of meetings ongoing at the corresponding time point.
- The expression
- Find the Maximum Value:
- The maximum value in the accumulated
deltaarray 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,
deltais all zeros. - After processing the intervals,
deltaat 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.
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.
-
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; } } // Solution 2 class Solution { public int minMeetingRooms(int[][] intervals) { Map<Integer, Integer> d = new TreeMap<>(); for (var e : intervals) { d.merge(e[0], 1, Integer::sum); d.merge(e[1], -1, Integer::sum); } int ans = 0, s = 0; for (var e : d.values()) { s += e; ans = Math.max(ans, s); } return ans; } } -
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()); } }; // Solution 2 class Solution { public: int minMeetingRooms(vector<vector<int>>& intervals) { map<int, int> d; for (const auto& e : intervals) { d[e[0]]++; d[e[1]]--; } int ans = 0, s = 0; for (auto& [_, v] : d) { s += v; ans = max(ans, s); } return ans; } }; -
''' 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 # Solution 2 class Solution: def minMeetingRooms(self, intervals: List[List[int]]) -> int: d = defaultdict(int) for l, r in intervals: d[l] += 1 d[r] -= 1 ans = s = 0 for _, v in sorted(d.items()): s += v ans = max(ans, s) 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) } // Solution 2 func minMeetingRooms(intervals [][]int) (ans int) { d := make(map[int]int) for _, e := range intervals { d[e[0]]++ d[e[1]]-- } keys := make([]int, 0, len(d)) for k := range d { keys = append(keys, k) } sort.Ints(keys) s := 0 for _, k := range keys { s += d[k] ans = max(ans, s) } return } -
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 } } // Solution 2 use std::collections::HashMap; impl Solution { pub fn min_meeting_rooms(intervals: Vec<Vec<i32>>) -> i32 { let mut d: HashMap<i32, i32> = HashMap::new(); for interval in intervals { let (l, r) = (interval[0], interval[1]); *d.entry(l).or_insert(0) += 1; *d.entry(r).or_insert(0) -= 1; } let mut times: Vec<i32> = d.keys().cloned().collect(); times.sort(); let mut ans = 0; let mut s = 0; for time in times { s += d[&time]; ans = ans.max(s); } 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; } // Solution 2 function minMeetingRooms(intervals: number[][]): number { const d: { [key: number]: number } = {}; for (const [l, r] of intervals) { d[l] = (d[l] || 0) + 1; d[r] = (d[r] || 0) - 1; } let [ans, s] = [0, 0]; const keys = Object.keys(d) .map(Number) .sort((a, b) => a - b); for (const k of keys) { s += d[k]; ans = Math.max(ans, s); } return ans; }