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)。
➡️
