KK's blog

每天积累多一些

0%

LeetCode 253 Meeting Rooms II

Posted on Edited on Disqus:

LeetCode 253 Meeting Rooms II

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.

题目大意：

输入[[0, 30],[5, 10],[15, 20]]表示每个会议的开始结束时间，求最少需要多少会议室能够安排所有的会议。

最小堆解题思路：

基于merging interval题目，首先按start排序。并且merge条件是start小于上一个会议的end。

  1. 写几个例子感受一下。

    有两个重叠的会议，现在插入新的会议。是否再需要一个会议室取决于该新会议的开始时间小于这两个目前会议的终止时间的最小值。
    所以思路是用End time min-heap维护目前会议End time。若新会议start time小于堆顶元素，入栈且activeMeeting++，否则循环地出栈且activeMeeting–直到
    start time小于堆顶。
    这过程activeMeeting的最大值即所求。
    最坏情况是所有会议都重叠，复杂度为n* 2logn因为n个元素入堆出堆各一次，所以复杂度为nlogn，但会议一般不会集中，平均情况比排序法稍优。

注意事项：

  1. Heap为结束时间的heap。
  2. 类似于递减栈模板，用开始时间与堆顶的结束时间比较（表示这些会议均已结束），若大于堆顶，连续出堆。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
	intervals.sort()
	heap = [] # heap for end time
	max = 0
	for i in range(len(intervals)):
		# start time of the new meeting is earlier than on-going endtime
		while heap and intervals[i][0] >= heap[0]:
			heappop(heap)
		heappush(heap, (intervals[i][1]))
		if len(heap) > max:
			max = len(heap)
	return max

算法分析：

由于输入无序，所以先要排序O(nlogn), 而循环复杂度为O(nlogk), 所以总时间复杂度为O(nlogn)，空间复杂度O(k), k为所求也就是需要的会议室数。

排序法解题思路(推荐)：

  1. 证明解与具体间隔无关，只与end time的值有关。
  2. 基于1和2，对end time进行排序，题解只与start-end的相对顺序有关。既然这样，我们可以把所有start，end一起排序，也就是按时间轴排列，排成一个2n大小的数组，
    遇到start，activeMeeting++，遇到end，activeMeeting–。 这过程activeMeeting的最大值即所求。
    当然，上述方法直观，但实现起来需要建立一个class Node{value, startOrEnd}。本质上等价于对排序后的start数组和排序后的end数组进行合并排序。
    合并排序的结果等价于时间轴上两个数组的统一排序。当然，不需要剩余部分的合并排序，因为这部分不会增加activeMeeting的值。

解题步骤：

  1. 排序start
  2. 排序end
  3. 合并排序，start小就activeMeeting++，否则activeMeeting–。求activeMeeting的最大值。

注意事项：

  1. 若endpoint值相同情况下，要确保第二个排序先结束点，再出发点，因为相同点不算有重复飞机

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
	start = [(i[0], 1) for i in intervals]
	ends = [(i[1], -1) for i in intervals]
	endpoints = start + ends
	endpoints.sort()
	active_meetings, max = 0, 0
	for i in range(len(endpoints)):
		if endpoints[i][1] == 1:
			active_meetings += 1
		else:
			active_meetings -= 1
		if active_meetings > max:
			max = active_meetings
	return max

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n)。

Free mock interview