Python 实现 汇总区间 算法 - 找出覆盖数组所有数字的最少区间范围列表

Python 实现 汇总区间 算法 - 找出覆盖数组所有数字的最少区间范围列表

给定一个无重复元素的有序整数数组 nums。返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x。

算法思路

1. 对 nums 进行排序，保证区间范围的起始和结束位置都是有序的。
2. 遍历排序后的 nums，维护一个当前区间范围 [start, end]。
3. 如果当前遍历到的区间范围的起始位置 intervals[i][0] 小于或等于当前区间的结束位置 end，则更新当前区间的结束位置为 end = max(end, intervals[i][1])。
4. 否则，将当前区间范围 [start, end] 添加到结果列表 res 中，并将当前区间范围更新为 start, end = intervals[i][0], intervals[i][1]。
5. 最后，将最后一个区间范围添加到结果列表 res 中。

Python 代码实现

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        intervals.sort()
        res = []
        start, end = intervals[0][0], intervals[0][1]
        for i in range(1, len(intervals)):
            if intervals[i][0] <= end:
                end = max(end, intervals[i][1])
            else:
                res.append([start, end])
                start, end = intervals[i][0], intervals[i][1]
        res.append([start, end])
        return res

代码解释

1. intervals.sort() 对区间范围进行排序，保证起始位置和结束位置都是有序的。
2. res = [] 初始化一个结果列表，用于存储最终的区间范围列表。
3. start, end = intervals[0][0], intervals[0][1] 初始化当前区间范围。
4. 循环遍历 intervals 列表，判断当前区间范围的起始位置是否小于或等于当前区间的结束位置，如果是，则更新当前区间的结束位置，否则将当前区间范围添加到结果列表中，并更新当前区间范围。
5. 最后，将最后一个区间范围添加到结果列表中。

示例

intervals = [[1,3],[2,6],[8,10],[15,18]]
result = Solution().merge(intervals)
print(result) # Output: [[1, 6], [8, 10], [15, 18]]

总结

本文介绍了如何使用 Python 实现 汇总区间 算法，并提供了详细的代码解释和示例。该算法可以用于找出覆盖无重复元素有序整数数组中所有数字的最小有序区间范围列表，在实际应用中具有广泛的用途。