253. Meeting Rooms II (Python)

Related Topic

Heap. Greedy.

Description

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.

Sample I/O

Example 1

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2

Input: [[7,10],[2,4]]
Output: 1

Note

input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Methodology

You can use greedy or heap to solve the question.

Greedy: We need to wrap the end time of interval as one room and append it to rooms. First we sort the interval. Then we iterate the given interval, if the current interval’s start time is bigger or equal than any room’s end time in rooms, we will append the current interval’s end time to this room; if the current interval’s start time is not bigger or not equal than any room’s end time in rooms, we will wrap this end time of the current interval as one room and append it to rooms. Finally, the result will be the size of the rooms.

Heap: We use min heap. First we sort the intervals then iterate the intervals, for each interval, if the start time is greater or equal than the heap[0] we will pop from heap and push the interval’s end time into heap. Otherwise, we will just push the interval’s end time into heap. Finally, the result will be the size of heap.

Greedy Solution:

def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        size = len(intervals)
        if size<=1: return size
        sorted_intervals = sorted(intervals)
        rooms=[[sorted_intervals[0][1]]]
        for i in range(1,size):
            booked = False
            for room in rooms:
                if sorted_intervals[i][0]>=room[-1]:
                    room.append(sorted_intervals[i][1])
                    booked = True
                    break
            if not booked:rooms.append([sorted_intervals[i][1]])
        return len(rooms)

BigO

Time complexity : O($n^2$) where n is the size of input.

Heap Solution:

def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        size = len(intervals)
        if size<=1: return size
        heap = []
        for interval in sorted(intervals):
            if heap and interval[0]>=heap[0]:
                heapq.heappushpop(heap,interval[1])
            else:
                heapq.heappush(heap,interval[1])
        return len(heap)

BigO

Time complexity : O(nlogn) where n is the size of input.