253. Meeting Rooms II - cocoder39/coco39_LC GitHub Wiki

253. Meeting Rooms II

Notes 2023:

Option 1: priority queue

simulate how to arrange meeting rooms:

  1. start with the one starting earlier (so we sort intervals)
  2. when handling a new interval, we check at the point this new meeting starts, was any meeting over (end time <= start time of the new meeting): brute force -> priority queue
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        min_heap = []
        res = 0
        for start, end in intervals:
            while min_heap and start >= min_heap[0]: # 1 room is needed for back to back meetings
                heapq.heappop(min_heap)
            
            heapq.heappush(min_heap, end)

            res = max(res, len(min_heap))
        return res

Option 2

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        events = []
        for start, end in intervals:
            events.append((start, 1))
            events.append((end, -1))
        events.sort()
        
        active = 0
        res = 0
        for timestamp, delta in events:
            active += delta
            res = max(res, active)
        return res

suppose 2 rooms are needed for back to back meetings

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        events = []
        for start, end in intervals:
            events.append((start, -1))
            events.append((end, 1))
        # end goes first when end and start are identical because 1 room is needed for back2back minMeetingRooms
        # to let start goes first (eg, 2 rooms are needed for back2back meetins)
        events.sort()

        count = 0
        res = 0
        for event, delta in events:
            count -= delta
            res = max(res, count)
        return res

=================================================================================================

Update on Mar. 3, 2021: Counting boundary is the best solution for this kind of problem

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        events = []
        for start, end in intervals:
            events.append((start, 1))
            events.append((end, -1))
        events.sort()
        
        active = 0
        res = 0
        for timestamp, delta in events:
            active += delta
            res = max(res, active)
        return res

Updated before Mar. 3, 2021: first attempt using line sweep template

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        startEvents = [(start, 's', end) for start, end in intervals]
        endEvents = [(end, 'e', None) for start, end in intervals]
        
        # when end event and start event happen at exact same time
        # pushing end event first 
        events = sorted(startEvents + endEvents)
        
        minHeap = [(float("inf"), 0)]
        res = 0
        for start, state, end in events:
            while start >= minHeap[0][0]:
                heapq.heappop(minHeap)
            
            if state == 's':
                heapq.heappush(minHeap, (end, start))
            
            res = max(res, len(minHeap))
        return res - 1

Simplify

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        
        minHeap = [float("inf")]
        res = 0
        for start, end in intervals:
            while start >= minHeap[0]:
                heapq.heappop(minHeap)
            
            heapq.heappush(minHeap, end)
            
            res = max(res, len(minHeap))
        return res - 1

================================================================================

Conclusion: solution 1 (min heap), solution 2 (vector), solution 3 (vector) are same. The explanation of solution 2 is same as solution 1, but actually solution 2 is same as solution 3.

Main idea is using the size of min heap to record how many rooms are necessary. if (intervals[i].start >= pq.top()), meeting i will be hold in the room whose end time is earliest. Update the end time of that room; else if (intervals[i].start < pq.top()), one more room is required.

min heap is achieved by priority_queue<int, vector<int>, greater<int>> pq

T = O(N * log N) S = O(N)

int minMeetingRooms(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), [](Interval i1, Interval i2){
            return i1.start <= i2.start;
        });
        
        priority_queue<int, vector<int>, greater<int>> pq; //pq.top() is the most recent avaiable room
        for (int i = 0; i < intervals.size(); i++) {
            if (! pq.empty() && intervals[i].start >= pq.top()) { //no conflict
                pq.pop(); 
            }
            pq.push(intervals[i].end); //update most recent available time for current room
        }
        return pq.size();
    }

another idea is also O(n * log n), but a litter tricky. traversal start time, and compare the current start time with the soonest end time. kinda like min heap solution

int minMeetingRooms(vector<Interval>& intervals) {
        vector<int> starts(intervals.size());
        vector<int> ends(intervals.size());
        for (int i = 0; i < intervals.size(); i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());

        int res = 0;
        int soonest_end = 0; //index in ends
        for (int i = 0; i < starts.size(); i++) {
            if (starts[i] < ends[soonest_end]) {
                res++;
            }
            else { //current meeting can use the most recently finished room
                //update soonest end time
                soonest_end++;
            }
        }
        return res;
    }

easiest method. time is O(2n * log(2n))

  • (1) use map<timestamp, count> to get sorted sequence
  • (2) since one room is enough for two meetings if one's start time is the other's end time, we use count +1 for opening a room, -1 for closing a room
int minMeetingRooms(vector<Interval>& intervals) {
        map<int, int> mp; 
        for (int i = 0; i < intervals.size(); i++) {
            mp[intervals[i].start]++;
            mp[intervals[i].end]--;
        }
        
        int res = 0, num = 0;
        for (auto &i : mp) {
            num += i.second;
            res = max(res, num);
        }
        return res;
    }

this method can be used to solve a follow up: max overlap point or interval

#include <iostream>
#include <vector>

using namespace std;

class Interval {
public:
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

Interval maxOverlap(vector<Interval>& intervals) {
    int sz = intervals.size();
    vector<int> starts(sz), ends(sz);
    for (int i = 0; i < sz; i++) {
        starts[i] = intervals[i].start;
        ends[i] = intervals[i].end;
    }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());

    Interval res;
    int high = 0, num = 0;
    int s = 0, e = 0;
    while (s < sz && e < sz) {
        if (starts[s] <= ends[e]) {
            num++;
            if (high < num) {
                high = num;
                res.start = starts[s];
                res.end = ends[e];
            }
            s++;
        } else {
            num--;
            e++;
        }
    }
    return res;
}

int main() {
    vector<Interval> intervals{Interval(0, 30), Interval(5, 17), Interval(15, 20)};
    Interval res = maxOverlap(intervals);
    cout << res.start << " to " << res.end << endl;
    return 0;
}
⚠️ **GitHub.com Fallback** ⚠️