Description
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Example 2:
Input: intervals = [[7,10],[2,4]]
Output: 1
Constraints:
1 Solution
Heap
Solved after hints…
Think about how we would approach this problem in a very simplistic way. We will allocate rooms to meetings that occur earlier in the day v/s the ones that occur later on, right?
If you’ve figured out that we have to sort the meetings by their start time, the next thing to think about is how do we do the allocation?
There are two scenarios possible here for any meeting. Either there is no meeting room available and a new one has to be allocated, or a meeting room has freed up and this meeting can take place there.
So use a min-heap to store the ending time, every time we visit a new interval, compare the start time with the earliest ending time. If the start time begins later than the earliest ending time, then we could free up the room and allocate the room to the new interval. Otherwise we need to assign a new room for the new interval.
Time complexity:
o
(
n
log
服务器托管网 n
)
o(nlog n )
o(nlogn)
Space complexity:
o
(
n
)
o(n)
o(n)
Sort + sweep
For all start, +1 at the point, and -1 for all ending points. Then sweep through all the points.
Time complexity:
o
(
n
log
n
)
o(nlog n)
o(nlogn)
Space complexity:
o
(
1
)
o(1)
o(1)
Code
Heap
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
heap = []
intervals.sort(key=lambda x: x[0])
res = 0
for i in range(len(intervals)):
if heap and heap[0] intervals[i][0]:
服务器托管网 heapq.heappop(heap)
heapq.heappush(heap, intervals[i][1])
res = max(res, len(heap))
return res
Sort + sweep
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
meetings = {}
for start, end in intervals:
meetings[start] = meetings.get(start, 0) + 1
meetings[end] = meetings.get(end, 0) - 1
points = sorted(meetings)
res = 0
room = 0
for each_point in points:
room += meetings[each_point]
res = max(res, room)
return res
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
一、前言 在 LXD 虚拟化平台（1）：简介 初步介绍了 LXD 虚拟化平台的基本概念与初始化安装，接下来的会详细讲解 LXD 平台的各项功能。 本文聚焦在 LXD 镜像管理管理功能上。 二、镜像管理 和容器镜像类似，LXD 也有镜像管理的功能。但 LXD 本…
