Merge Intervals（合并区间）

题目 / Problem

中文： 给定一个区间数组 intervals，其中 intervals[i] = [starti, endi]。合并所有相互重叠的区间，并返回一组互不重叠、且覆盖输入中全部区间的结果。

English: Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return an array of non-overlapping intervals that covers every interval in the input.

示例 / Examples

Example 1

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

区间 [1,3] 和 [2,6] 重叠，因此合并为 [1,6]。
Intervals [1,3] and [2,6] overlap, so they are merged into [1,6].

Example 2

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

两个区间在端点 4 相交，也被视为重叠。
The intervals share endpoint 4, so they are considered overlapping.

Example 3

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

排序后区间变为 [[1,4],[4,7]]，两者合并为 [1,7]。
After sorting, the intervals become [[1,4],[4,7]] and merge into [1,7].

约束 / Constraints

• 1 <= intervals.length <= 10^4
• intervals[i].length === 2
• 0 <= starti <= endi <= 10^4

解题思路：排序后合并 / Approach: Sort and Merge

如果按照区间起点从小到大排序，那么当前区间只需要与结果数组中的最后一个区间比较。
Once intervals are sorted by starting point, each current interval only needs to be compared with the last interval in the result.

设最后一个已合并区间为 [lastStart, lastEnd]，当前区间为 [start, end]：
Let the last merged interval be [lastStart, lastEnd] and the current interval be [start, end]:

• 如果 start <= lastEnd，两个区间重叠，将结束位置更新为 max(lastEnd, end)。
  If start <= lastEnd, they overlap; update the end to max(lastEnd, end).
• 如果 start > lastEnd，两个区间不重叠，将当前区间加入结果。
  If start > lastEnd, they do not overlap; append the current interval.

注意判断条件必须是 start <= lastEnd，而不是 start < lastEnd，因为共享端点也属于重叠。
The condition must be start <= lastEnd, not start < lastEnd, because sharing an endpoint also counts as overlap.

算法步骤 / Algorithm

1. 按照每个区间的起点升序排序。
   Sort all intervals by their starting values.
2. 将第一个区间的副本放入结果数组。
   Put a copy of the first interval into the result.
3. 从第二个区间开始遍历。
   Iterate from the second interval.
4. 如果当前区间与结果中的最后一个区间重叠，更新最后一个区间的终点。
   If the current interval overlaps the last result interval, update its ending value.
5. 否则，将当前区间作为一个新区间加入结果。
   Otherwise, append the current interval as a new result interval.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);

  const merged = [[...intervals[0]]];

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    const last = merged[merged.length - 1];

    if (start <= last[1]) {
      // 当前区间与最后一个区间重叠
      // The current interval overlaps the last one
      last[1] = Math.max(last[1], end);
    } else {
      // 没有重叠，开始一个新的合并区间
      // No overlap, so start a new merged interval
      merged.push([start, end]);
    }
  }

  return merged;
}

执行过程 / Walkthrough

以 intervals = [[1,3],[2,6],[8,10],[15,18]] 为例：
For intervals = [[1,3],[2,6],[8,10],[15,18]]:

最终结果为：
The final result is:

[[1,6],[8,10],[15,18]]

为什么排序有效？ / Why Does Sorting Work?

排序后，后续区间的起点不会小于当前区间的起点。因此，如果当前区间无法与结果中的最后一个区间合并，它也不可能与更早、终点更靠前的区间合并。
After sorting, later intervals never start before the current one. Therefore, if the current interval cannot merge with the last result interval, it cannot merge with any earlier interval whose ending point is even farther left.

这样，每个区间在排序后只需处理一次。
As a result, every interval only needs to be processed once after sorting.

复杂度 / Complexity

设 n = intervals.length。
Let n = intervals.length.

• 时间复杂度 / Time: O(n log n)，主要来自排序；合并过程为 O(n)。
  Sorting dominates the runtime; the merge pass takes O(n).
• 空间复杂度 / Space: O(n)，用于保存返回结果；排序本身的额外空间取决于 JavaScript 引擎的实现。
  O(n) is used for the returned result; extra sorting space depends on the JavaScript engine.

易错点 / Common Pitfalls

• 必须先按区间起点排序，不能假设输入已经有序。
  Sort by starting point first; the input is not guaranteed to be sorted.
• 共享端点也算重叠，所以使用 start <= last[1]。
  Shared endpoints count as overlap, so use start <= last[1].
• 合并后的终点应使用 Math.max(last[1], end)，不能直接赋值为 end。
  Use Math.max(last[1], end) for the merged ending value instead of assigning end directly.
• JavaScript 默认的 sort() 按字符串排序，必须传入比较函数。
  JavaScript's default sort() is lexicographic, so a numeric comparator is required.
• 如果不希望修改输入数组，可以先复制再排序：const sorted = [...intervals].sort(...)。
  To avoid mutating the input array, copy it before sorting: const sorted = [...intervals].sort(...).