Leetcode 253: Meeting Rooms II

 

Code

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0
        
        timeline = []
        for i in intervals:
            timeline.append(('start', i.start))
            timeline.append(('end', i.end))
            
        # sort timeline tuples by time first then by 'start' or 'end' tag
        # e.g. ('end', 13) < ('start', 13)
        timeline = sorted(timeline, key=lambda x: (x[1], x[0]))
        
        room = 0
        max_room = 0
        for k, v in timeline:
            if k == 'start':
                room += 1
            else:
                room -= 1
            if room > max_room:
                max_room = room
        
        return max_room
                

 

Idea

Create a timeline, a list of tuples. Each tuple marks a “start” or “end” tag with the time. Then sort the timeline and start traversing it. Whenever you see a start time, that means a new room is requested. Whenever you see an end time, that means a room is returned. 

 

You can also use heap to solve this problem: https://discuss.leetcode.com/topic/25904/python-heap-solution-with-comments

Code

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

from heapq import *

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        intervals = sorted(intervals, key=lambda x: x.start)
        heap = []
        for i in intervals:
            # if the new meeting happens after the earliest meeting ends,
            # replace the earliest ending meeting with the new meeting
            if heap and i.start >= heap[0]:
                heappop(heap)
                heappush(heap, i.end)
            else:
                heappush(heap, i.end)

        return len(heap)