Meeting Rooms I & II

题目描述

1. 求是否有冲突
2. 求需要多少个room

思路

Intervals的题目，首先我们按照start time sort一下，这样便于后面的处理。sort用到的 是python的sorted和key paramer.

intervals = sorted(intervals, key=lambda interval: interval.start)

１的话因为start time后面的必然在后面开始，只要确定开始的时候前面的已经结束就可以了， 而且只需要比较前面一个。

２的话有点像airline那个线扫描的题目，我们可以用一个heap来保存前面的end time,这样 当遇到一个新的start time时，只需要将在这之前end的meeting都pop掉就可以了。并且在 这个过程中计算需要的room的数量。

Solution

from operator import itemgetter, attrgetter
from heapq import *

class Solution(object):
    def minMeetingRooms(self, intervals):
        if not interval:
            return 0
        intervals = sorted(intervals, key=lambda interval:interval.start)
        length = len(intervals)

        cur_num = 0
        max_num = 0
        end_times = []
        for i in range(length):
            cur_num += 1
            heappush(end_times, intervals[i].end)
            while end_times and end_times[0] <= intervals[i].start:
                heappop(end_times)
                cur_num -= 1
            max_num = max(max_num, cur_num)

        return max_num