难度: Medium
Submission
运行时间: 50 ms
内存: 22.0 MB
from typing import List
class Solution:
def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:
# Initialize pointers for slots1 and slots2
p1 = 0
p2 = 0
# Sort the slots based on their start times
slots1, slots2 = sorted(slots1), sorted(slots2)
# Iterate through both lists to find overlapping slots
while p1 < len(slots1) and p2 < len(slots2):
# Extract start and end times for both slots
s1, e1 = slots1[p1]
s2, e2 = slots2[p2]
# Calculate the overlap between the current slots
left, right = max(s1, s2), min(e1, e2)
# If the overlap is greater than or equal to the required duration,
# return the available time slot
if right - left >= duration:
return [left, left + duration]
# Move to the next slot in the list that ends earlier
if e1 <= e2:
p1 += 1
else:
p2 += 1
# If no suitable slot is found, return an empty list
return []
# Sorting both slots lists: O(n log n), where n is the total number of slots across both lists.
# Iterating through the sorted lists: O(n), where n is the total number of slots across both lists.
# Overall time complexity: O(n log n).
# Space complexity: O(1), as only a constant amount of additional space is used.
Explain
本题解的核心思路是找出两个时间段列表中的共同空闲时间，并确保这段时间至少有给定的持续时间（duration）。首先，通过排序两个时间段列表以便按时间顺序处理。使用两个指针分别遍历两个列表，寻找两个时间段的交集。如果交集的长度至少为duration，则返回该时间段的开始和结束时间。如果当前比较的两个时间段没有足够的交集或者一个时间段比另一个早结束，则移动结束时间较早的时间段的指针，继续寻找可能的交集。如果遍历完毕后仍无合适时间段，则返回空列表。
时间复杂度: O(n log n)
空间复杂度: O(1)
from typing import List
class Solution:
def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:
# Initialize pointers for slots1 and slots2
p1 = 0
p2 = 0
# Sort the slots based on their start times
slots1, slots2 = sorted(slots1), sorted(slots2)
# Iterate through both lists to find overlapping slots
while p1 < len(slots1) and p2 < len(slots2):
# Extract start and end times for both slots
s1, e1 = slots1[p1]
s2, e2 = slots2[p2]
# Calculate the overlap between the current slots
left, right = max(s1, s2), min(e1, e2)
# If the overlap is greater than or equal to the required duration,
# return the available time slot
if right - left >= duration:
return [left, left + duration]
# Move to the next slot in the list that ends earlier
if e1 <= e2:
p1 += 1
else:
p2 += 1
# If no suitable slot is found, return an empty list
return []
Explore
在处理两个时间段列表之前进行排序是为了简化时间段交集的查找过程。通过将时间段按开始时间排序，可以确保在遍历时，每个列表中的时间段都是按时间顺序出现。这样，在查找交集时，只需要比较当前两个列表中的时间段。若当前时间段无交集，可以直接移动结束时间较早的时间段的指针，有效地减少了不必要的比较，从而提高算法的效率。排序的时间复杂度为O(n log n)，但它为整个查找过程提供了结构上的便利，使得后续的交集查找过程能够以线性时间完成，即O(n)。因此，虽然排序增加了前期的计算成本，但总体上优化了算法的时间效率。
选择移动结束时间较早的时间段的指针是为了有效地缩小查找范围，并避免无效的比较。当一个时间段的结束时间较早时，它与其他时间段的可能交集也就结束了。继续比较该时间段已无意义，因此移动其指针到下一个时间段，是一种减少无效操作并加速查找过程的方法。这种选择使算法只在有可能找到有效交集时才进行比较，避免了不必要的比较，从而提高了算法的效率。同时，这种方法保证了算法能够遍历所有可能的时间段组合，确保找到所有可行的交集，不会漏掉任何可能的结果。
算法确保找到的时间段内有至少给定的持续时间（duration）是通过计算两个时间段的交集并检查这个交集的长度来实现的。具体操作如下：首先，算法通过取两个时间段的最大开始时间和最小结束时间来确定交集的开始和结束时间。然后，算法计算交集的长度，即结束时间减去开始时间。如果这个长度大于或等于给定的持续时间（duration），那么这个时间段就被认为是有效的，并将其作为结果返回。这种方法通过简单的数学计算确保了时间段的有效性，并且容易实现和理解。