DEV Community ·

LeetCode 思考：合并区间

💡 原文英文，约500词，阅读约需2分钟。

📝

内容提要

给定一个区间数组，首先对其进行排序，然后逐个检查并合并重叠的区间，最终返回不重叠的区间数组。该算法的时间复杂度为O(n log n)，空间复杂度为O(n)。

🎯

给定一个区间数组，合并所有重叠的区间，返回不重叠的区间数组。
示例输入: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]，输出: [[1, 6], [8, 10], [15, 18]]。
首先对区间进行排序，以便后续比较。
初始化结果数组，初始时包含排序后的第一个区间。
检查当前区间与最后合并区间的重叠情况，决定是否合并。
如果不重叠，将当前区间添加到结果中；如果重叠，更新最后合并区间的结束值。
最终返回合并后的结果数组。
算法的时间复杂度为O(n log n)，空间复杂度为O(n)。

🔎

该算法的时间复杂度为O(n log n)，主要来源于对区间的排序过程。虽然合并操作的复杂度为O(n)，但排序是主导因素。在处理大规模数据时，理解这一点有助于评估算法的效率。

合并区间的算法在许多实际场景中都有应用，例如日程安排、资源分配等。通过有效合并重叠区间，可以优化资源使用，避免冲突，提高工作效率。

在判断区间是否重叠时，需要注意定义：两个区间重叠的条件是一个区间的起始点小于或等于另一个区间的结束点。理解这一点对于正确实现合并逻辑至关重要。

❓

首先对区间进行排序，然后逐个检查并合并重叠的区间，最终返回不重叠的区间数组。

算法的时间复杂度为O(n log n)，空间复杂度为O(n)。

示例输入为 intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]，输出为 [[1, 6], [8, 10], [15, 18]]。

两个区间不重叠的条件是一个区间的开始严格大于另一个区间的结束，或结束严格小于另一个区间的开始。

初始化结果数组，检查当前区间与最后合并区间的重叠情况，决定是否合并或添加当前区间。

算法实现示例为：首先排序区间，然后遍历区间，检查重叠并更新结果数组。

🏷️