56、合并区间

;(function () {
  /**
   * 56. 合并区间
   * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
   * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
   *
   * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
   * 输出：[[1,6],[8,10],[15,18]]
   * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
   *
   * 输入：intervals = [[1,4],[4,5]]
   * 输出：[[1,5]]
   * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
   *
   */

  // 关键词： 数组 / 排序
  function merge(intervals: number[][]): number[][] {
    // 方法一：
    // 1. 二维数组排序
    let sortArr = intervals.sort((a, b) => a[0] - b[0])
    // console.log(sortArr)
    let start: number = sortArr[0][0]
    let end: number = sortArr[0][1]
    let ans: number[][] = []
    sortArr.forEach((item, index) => {
      if (item[0] < end || item[0] === end) {
        end = item[1] > end ? item[1] : end
      } else {
        ans.push([start, end])
        start = item[0]
        end = item[1]
      }
      if (index === intervals.length - 1) {
        ans.push([start, end])
      }
    })
    return ans

    // 方法二：
  }

  // let intervals = [[1,3],[2,6],[8,10],[15,18]]
  let intervals = [
    [2, 6],
    [8, 10],
    [1, 3],
    [15, 18]
  ]
  let intervals2 = [
    [2, 6],
    [8, 10],
    [1, 3],
    [9, 18]
  ]
  let intervals3 = [
    [1, 4],
    [4, 5]
  ]
  let intervals4 = [[1, 3]]
  console.log(merge(intervals)) // [1, 6], [8, 10], [15, 18]
  console.log(merge(intervals2)) // [1, 6], [8, 18]
  console.log(merge(intervals3)) // [1, 5]
  console.log(merge(intervals4)) // [1, 3]
})()