难度: Medium
Submission
运行时间: 1252 ms
内存: 81.2 MB
from typing import List
class Solution:
def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:
# Step 1: Sort the ranges by start position
ranges.sort(key=lambda x: x[0])
# Initialize variables for tracking uncovered ranges
uncovered_ranges = [] # To store the uncovered ranges
start = 0 # Start of the current uncovered range
# Iterate through the sorted ranges to find uncovered ranges
for i in range(len(ranges)):
# Check if there is an uncovered range before the current range
if start < ranges[i][0]:
uncovered_ranges.append([start, ranges[i][0] - 1])
# Update the start of the next uncovered range
start = max(start, ranges[i][1] + 1)
# Check if there is an uncovered range after the last range
if start < n:
uncovered_ranges.append([start, n - 1])
return uncovered_ranges
Explain
解题思路是首先对给定的区间按照起始位置进行排序，然后遍历排序后的区间列表，找出每个区间之间未被覆盖的部分。通过维持一个变量 `start` 来标记当前未覆盖区间的起始点。在遍历每一个区间时，如果 `start` 小于当前区间的起始位置，说明存在一个未覆盖的区间，将其加入结果列表。随后更新 `start` 的值为当前区间结束位置加一。最后，还需要检查在最后一个区间结束后是否还有未覆盖的区间直到 n。
时间复杂度: O(m log m)
空间复杂度: O(m)
from typing import List
class Solution:
def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:
# Step 1: Sort the ranges by start position
ranges.sort(key=lambda x: x[0])
# Initialize variables for tracking uncovered ranges
uncovered_ranges = [] # To store the uncovered ranges
start = 0 # Start of the current uncovered range
# Iterate through the sorted ranges to find uncovered ranges
for i in range(len(ranges)):
# Check if there is an uncovered range before the current range
if start < ranges[i][0]:
uncovered_ranges.append([start, ranges[i][0] - 1])
# Update the start of the next uncovered range
start = max(start, ranges[i][1] + 1)
# Check if there is an uncovered range after the last range
if start < n:
uncovered_ranges.append([start, n - 1])
return uncovered_ranges
Explore
对区间按起始位置进行排序的目的是为了确定每个区间开始的准确顺序，从而便于找出它们之间的未覆盖区间。如果在排序中同时考虑结束位置，可能会导致处理复杂化，因为即使一个区间早于另一个区间结束，但如果它开始得更晚，仍可能覆盖前一个区间的部分或全部。因此，首先按起始位置排序可以简化逻辑，确保我们能从左至右检查每个潜在的未覆盖区间。
在这种情况下，下一个区间的起始位置恰好是当前区间结束位置的下一个位置，因此没有留下未覆盖的空间。`start`变量已经更新为当前区间的结束位置加一，这意味着它正好等于下一个区间的起始位置。因此，这种情况下不会添加新的未覆盖区间，算法会继续检查之后的区间。
算法通过在遍历完所有给定区间后，检查`start`变量与`n`的关系来确保此点。如果`start`小于`n`，这意味着从`start`到`n-1`之间的区间未被覆盖，因此这一部分会被添加到结果列表中作为最后一个未覆盖区间。这样可以确保算法不遗漏任何位于最后一个给定区间之后且直到`n-1`的未覆盖区间。
`n`代表考虑的区间内的最大边界值，即区间从0开始，直到`n-1`。在题解中，`n`用来标识在所有给定区间之后可能存在的未覆盖区间的结束位置。题解中通过检查在处理完所有给定区间之后`start`变量的值是否小于`n`，来确定是否还存在未覆盖区间，确保算法能覆盖从0到`n-1`的完整范围，这对理解题目范围和解题方法是至关重要的。