美文网首页leetcode
[中等] 253. 会议室 II

[中等] 253. 会议室 II

作者: 章光辉_数据 | 来源:发表于2020-06-14 16:31 被阅读0次

    欢迎关注 leetcode 专栏

    题目

    给定一个会议时间安排的数组,每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...] (si < ei),为避免会议冲突,同时要考虑充分利用会议室资源,请你计算至少需要多少间会议室,才能满足这些会议安排。

    示例 1:

    输入: [[0, 30],[5, 10],[15, 20]]
    输出: 2
    

    示例 2:

    输入: [[7,10],[2,4]]
    输出: 1
    

    链接:https://leetcode-cn.com/problems/meeting-rooms-ii

    解法

    常规解法

    思路就是:

    1. 对所有会议,按照开始时间排升序;
    2. 用贪心算法,每来一个新的会议,遍历所有会议室,如果有空的会议室(该会议室的结束时间早于等于当前会议的开始时间),则作为当前最优的选择,更新该会议室的结束时间,并停止循环
    3. 如果一个可用的会议室都没有,则新增会议室,并更新该会议室的结束时间。
    class Solution:
        def minMeetingRooms(self, intervals: List[List[int]]) -> int:
            rooms = []  # 记录各会议室的结束时间
            meetings = sorted(intervals, key=lambda x: x[0])  # 按开始时间升序
            for meeting in meetings:
                find = False
                for index, end_time in enumerate(rooms):
                    # 找到满足结束时间早于当前会议开始时间的会议室,并更新会议室的时间表
                    if end_time <= meeting[0]:
                        rooms[index] = meeting[1]
                        find = True
                        break
                # 如果没找到,则新增会议室
                if not find:
                    rooms.append(meeting[1])
            return len(rooms)
    

    时间复杂度为 O(N^2),分为两个部分:

    1. 对长度为 N 的会议进行排序,复杂度为 O(N*logN)
      1, 对 N 个会议分别执行查找和插入操作,最差情况下任意两两会议的时间都是冲突的,那么对第 i 个会议的查找次数为 i 次,1+2+...+n=n(n+1)/2,全程共插入 n(n+1)/2 次,插入 N 次,最差复杂度为 O(N^2) 。

    空间复杂度O(n),就看 rooms 的长度,最好的情况下 O(1),最差的情况下 O(n)。

    最小堆解法

    import heapq
    
    class Solution:
        def minMeetingRooms(self, intervals: list) -> int:
            rooms = []  # 记录各会议室的最早结束时间
            meetings = sorted(intervals, key=lambda x: x[0])  # 按开始时间升序
            for meeting in meetings:
                # 如果最早结束的会议室的结束时间比会议室时间要早,则先关闭该会议室
                if rooms and rooms[0] <= meeting[0]:
                    heapq.heappop(rooms)
                # 插入新的会议室到最小堆
                heapq.heappush(rooms, meeting[1])
            return len(rooms)
    

    时间复杂度为O(N*logN),分为两个部分:

    1. 对长度为 N 的会议进行排序,复杂度为 O(N*logN)
    2. 对 N 个会议分别执行弹出和插入操作,最差情况下任意两两会议的时间都是冲突的,每次弹出的复杂度为 1,每次插入的复杂度为 O(logN),N 个会议室的总复杂度为 O(N*logN)

    空间复杂度O(n),就看 rooms 的长度,最好的情况下 O(1),最差的情况下 O(n)。

    优先队列解法

    from queue import PriorityQueue
    
    class Solution:
        def minMeetingRooms(self, intervals: list) -> int:
            rooms = PriorityQueue()
            meetings = sorted(intervals, key=lambda x: x[0])  # 按开始时间升序
            for meeting in meetings:
                # 如果最早结束的会议室的结束时间比会议室时间要早,则先关闭该会议室
                if rooms.qsize() and rooms.queue[0] <= meeting[0]:
                    rooms.get()
                # 插入新的会议室到优先队列
                rooms.put(meeting[1])
            return rooms.qsize()
    

    虽然用优先队列来实现,复杂度跟最小堆是一样的,但是算法实际执行的时候,耗时比较长,不知道是否是内部实现的时候有其他额外逻辑

    更多刷题,尽在 leetcode 专栏

    相关文章

      网友评论

        本文标题:[中等] 253. 会议室 II

        本文链接:https://www.haomeiwen.com/subject/vcpotktx.html