Meeting Rooms I/II

要点：这题和skyline类似，利用了interval start有序的特点，从左向右处理，用一个heap来动态表示当前占用rooms的时间段，所以heap的size就是room数。具体来说，

• heap是end time的min heap
• 当前？就是和新interval同时使用room的情况
• 如果min end<=新的interval.start，那么同一房间可以被这个interval重用。同时所有heap中end小的都要pop
• 如果min end>新的interval.start<min end：因为新interval.start比所有当前在heap中start的都晚，所以一定与所有heap中interval在某一点都有交集。所有max需要新房间，要push heap
• 所以在heap中的intervals必然都是在某一点互相重叠的
• 当然用endPoint sort + count的方法也可以。都是O(nlgn)，但不需要heap

https://repl.it/CfU6/4 (II)

错误点：不管是否pop，都要push新的：either 占新room or replace旧room

https://repl.it/CoP7 (I)

EDIT:

还有一类类似的题，是room (or 资源)有限，如何选最多的meeting。

# 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.

# For example,

# Given [[0, 30],[5, 10],[15, 20]],

# return 2.

# Hide Company Tags Google Facebook

# Hide Tags Heap Greedy Sort

# Hide Similar Problems (H) Merge Intervals (E) Meeting Rooms

from heapq import heappush, heappop

# 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

        """

        meetings = []

        intervals.sort(key=lambda interval:interval.start)

        count = 0

        while i in intervals:

            if not meetings or meetings[0]>i.start:

                heappush(meetings, i.end)

                i+=1

            else:

                heappop(meetings)

            count = max(count, len(meetings))

        return count

# Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

# For example,

# Given [[0, 30],[5, 10],[15, 20]],

# return false.

# Hide Company Tags Facebook

# Hide Tags Sort

# Hide Similar Problems (H) Merge Intervals (M) Meeting Rooms II

# Definition for an interval.

# class Interval(object):

#     def __init__(self, s=0, e=0):

#         self.start = s

#         self.end = e

class Solution(object):

    def canAttendMeetings(self, intervals):

        """

        :type intervals: List[Interval]

        :rtype: bool

        """

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

        intervals.sort(key=lambda interval: interval.start)

        for i in xrange(1, len(intervals)):

            if intervals[i].start<intervals[i-1].end:

                return False

        return True