LeetCode 冥想：合并间隔

让我们从合并间隔的描述开始：

给定一个间隔数组，其中间隔[i] = [start_i, end_i]，合并所有重叠间隔，并返回覆盖输入中所有间隔的非重叠间隔数组。

例如：

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

或者：

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

---

我们可以先对间隔进行排序，以便稍后可以轻松比较它们：

intervals.sort((a, b) => a[0] - b[0]);

此外，我们可以初始化一个结果数组，该数组最初保存新排序间隔的第一个元素：

let result = [intervals[0]];

我们需要跟踪最后一个合并间隔的结束，将其与我们正在查看的当前间隔的开始进行比较，以检查它们是否重叠。

注意 标题> 对于两个不重叠的间隔，其中一个的

Note

For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

开始应该严格大于比结束另一个或其中一个的末端应该严格小于 另一个的开始，如我们章节介绍中所述。 表>

如果它们不重叠，我们可以将该间隔添加到结果中。否则，我们需要更新“最后一个结尾”，有效地合并间隔：

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

并且，唯一要做的就是返回结果：

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

而且，这就是我们最终的解决方案在 TypeScript 中的样子：

intervals.sort((a, b) => a[0] - b[0]);

时间和空间复杂度

我们是对区间进行排序，内置的排序功能有 $O(nlogn）$O(n log n) 时间复杂度。 （循环是 $O(n)$O(n) ，但总体时间复杂度为 $O(nlogn）$O(n log n) ).

结果数组的大小会随着输入数组间隔大小的增加而增加，因此我们有 $O(n)$O(n) 空间复杂度。

---

接下来，我们将看一下“非重叠区间”一章中的最后一个问题。在那之前，祝您编码愉快。

以上是LeetCode 冥想：合并间隔的详细内容。更多信息请关注PHP中文网其他相关文章！