Heading

56.合并区间 (opens new window)

Tags: algorithms bloomberg facebook google linkedin microsoft twitter yelp array sort

Langs: c cpp csharp dart elixir erlang golang java javascript kotlin php python python3 racket ruby rust scala swift typescript

• algorithms
• Medium (49.82%)
• Likes: 2274
• Dislikes: -
• Total Accepted: 821.3K
• Total Submissions: 1.6M
• Testcase Example: '[[1,3],[2,6],[8,10],[15,18]]'

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

 

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

 

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

/*
 * @lc app=leetcode.cn id=56 lang=javascript
 *
 * [56] 合并区间
 */

// @lc code=start
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  if (intervals.length <= 1) {
    return intervals
  }

  let insertion
  for (let i = 1; i < intervals.length; i++) {
    insertion = intervals[i]
    let j = i
    while (j > 0 && insertion[0] < intervals[j - 1][0]) {
      intervals[j] = intervals[j - 1]
      j--
    }
    intervals[j] = insertion
  }

  const result = [intervals[0]]
  for (let i = 1; i < intervals.length; i++) {
    if (result[result.length - 1][1] >= intervals[i][0]) {
      result[result.length - 1][1] = Math.max(result[result.length - 1][1], intervals[i][1])
    } else {
      result.push(intervals[i])
    }
  }
  return result
}
// @lc code=end