[Leetcode]253. Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
Example 1:
Input: [[0, 30],[5, 10],[15, 20]] Output: 2

This problem could be solved using greedy strategy – after sorting the meetings based on the starting time, we would reuse the room of the earliest finished meeting when considering the new meeting.

Sort meetings first and scan them to find out the answer.

With that being said, there are two approaches – we can either choose two pointers or use heap.

Two pointers

The logic is that we would open a room for each meeting, unless that there’s a previous meeting being finished so that we could reuse that room. To achieve it, we have one pointer i to explore new meetings while using end to represent the meetings that are taking rooms. Each time when we find that start[i]>=ending[end], it means that the current meeting finishes after end and therefore could use that room.

Two pointers to scan meetings.
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        s,e = [e[0] for e in intervals],[e[1] for e in intervals]
        s.sort()
        e.sort()
        rooms = 0
        end = 0
        for i in range(len(intervals)):
            if s[i] < e[end]:
                rooms += 1
            else:
                end += 1
        return rooms

Min-heap

When a previous meeting is finished, we could reuse that room.

Similarly, this approach also utilises the logic that meetings could reuse rooms that become available again after the meetings are finished. The way it decides which room to reuse, however, relies on min-heap which returns the meeting that is finished earliest. One can treat the heap as the rooms holding different meetings: if the new meeting starts after the earliest possible finishing time for the ongoing meetings, then a new room is created for that meeting and the meeting should be pushed into the heap; or if it starts after, the meeting that is finished earliest could be popped out and the new meeting should be pushed into the heap reusing the room.

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x:(x[0]))
        pq = []
        for i in range(len(intervals)):
            if pq and pq[0] <= intervals[i][0]:
                heapq.heapreplace(pq,intervals[i][1])
            else:
                heapq.heappush(pq,intervals[i][1])
        return len(pq)
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments