56.merge-intervals.md

题目地址

https://leetcode.com/problems/merge-intervals/description/

题目描述

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

思路

• 先对数组进行排序，排序的依据就是每一项的第一个元素的大小。
• 然后我们对数组进行遍历，遍历的时候两两运算（具体运算逻辑见下）
• 判断是否相交，如果不相交，则跳过
• 如果相交，则合并两项

关键点解析

• 对数组进行排序简化操作
• 如果不排序，需要借助一些hack,这里不介绍了

代码

/*
 * @lc app=leetcode id=56 lang=javascript
 *
 * [56] Merge Intervals
 */
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */

function intersected(a, b) {
  if (a[0] > b[1] || a[1] < b[0]) return false;
  return true;
}

function mergeTwo(a, b) {
  return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
}
var merge = function(intervals) {
  // 这种算法需要先排序
  intervals.sort((a, b) => a[0] - b[0]);
  for (let i = 0; i < intervals.length - 1; i++) {
    const cur = intervals[i];
    const next = intervals[i + 1];

    if (intersected(cur, next)) {
      intervals[i] = undefined;
      intervals[i + 1] = mergeTwo(cur, next);
    }
  }
  return intervals.filter(q => q);
};