919 · 会议室 II - LintCode

Difficulty
easy
Tags
扫描线
优先队列
URL
https://www.lintcode.com/problem/919/?_from=problem_tag&fromId=undefined
Star
给定一系列的会议时间间隔intervals，包括起始和结束时间[[s1,e1],[s2,e2],...] (si < ei)，找到所需的最小的会议室数量。
Example1
输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
需要两个会议室
会议室1:(0,30)
会议室2:(5,10),(15,20)
Example2
输入: intervals = [(2,7)]
输出: 1
解释:
只需要1个会议室就够了

法1 扫描线

思路
同
🎳
391 · 数飞机 - LintCode 一样，都是求最大重复区间个数的
题解
"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    """
    @param intervals: an array of meeting time intervals
    @return: the minimum number of conference rooms required
    """
    def minMeetingRooms(self, intervals):
        # Write your code here
        if len(intervals) <= 1:
            return len(intervals)
        
        point = []
        for a in intervals:
            point.append([a.start, 1])
            point.append([a.end, -1])
        point.sort(key=lambda x:(x[0], x[1]))

        res, count = 0, 0
        for p in point:
            count += p[1]
            res = max(res, count)
        
        return res

法 2 优先队列

思路
按照会议开始时间升序排列，如果下一个会议开始时间大于上一个结束时间，说明上一个的会议室可以接着用。
先对会议开始时间进行升序排列。然后借助栈，先放进去最先开始的会议，然后按照排好的顺序依次往堆中放，堆是按照结束时间升序拍的。如果当前的会议开始时间晚于堆顶的结束时间，则堆顶的可以弹出来。
也可以用while循环，只不过用while的时候，需要把中间最大的堆长度保存下来。
先对intervals 按照 start 排序。之后建立一个PriorityQueue用来记录end。遍历intervals时，每一个interval的start如果和最小的end有冲突（PriorityQueue会自动poll最小的end），说明需要新的会议室，把这一个end加入队列。如果和最小的end没有冲突，可以把最小的end poll（）走，因为新的end取决于当前interval的end。最后队列元素的个数就是需要会议室的数目。
因为排过序，时间复杂度应该是 O（nlogn）。空间复杂度需要一个队列，应该是O（n）。
题解
"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""
import heapq
class Solution:
    """
    @param intervals: an array of meeting time intervals
    @return: the minimum number of conference rooms required
    """
    def minMeetingRooms(self, intervals):
        # Write your code here
        if len(intervals) <= 1:
            return len(intervals)
        
        intervals = [[i.start, i.end] for i in intervals ]
        intervals.sort()
        queue = []
        # 只存储结束时间到堆中
        heapq.heappush(queue, intervals[0][1])
        for i in range(1, len(intervals)):
            if intervals[i][0] >= queue[0]:
                heapq.heappop(queue)
            heapq.heappush(queue, intervals[i][1])
        
        return len(queue)
换成while的写法，记录中间状态
def minMeetingRooms(self, intervals):
        # Write your code here
        if len(intervals) <= 1:
            return len(intervals)
        
        intervals = [[i.start, i.end] for i in intervals ]
        intervals.sort()
        
        queue = []
        # 只存储结束时间到堆中
        res = 1
        heapq.heappush(queue, intervals[0][1])
        for i in range(1, len(intervals)):
            while intervals[i][0] >= queue[0]:
                heapq.heappop(queue)
            heapq.heappush(queue, intervals[i][1])
            res = max(res, len(queue))
        
        return res