56. 合并区间和区间判重

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

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
  // 1. 区间起始时间排序: 时间复杂度 O(nlogn)
  let _intervals = intervals.sort((a, b) => a[0] > b[0] ? 1 : -1);

  let result = [];

  // 2. 比较区间重叠的三种情况
  let previous = null;
  let current;
  for(let i = 0; i < _intervals.length; i++) {
    current = _intervals[i];

    if (previous === null) {
      previous = current;
    } else if (current[0] > previous[1]) {
      result.push(previous);
      previous = current;
    } else {
      previous[1] = Math.max(previous[1], current[1]);
    }
  }
  if (previous) {
    result.push(previous);
  }

  return result;
};

输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
  // 1. 区间起始时间排序: 时间复杂度 O(nlogn)
  let _intervals = intervals.sort((a, b) => a[0] > b[0] ? 1 : -1);

  // 2. 开始递归
  return _eraseOverlapIntervals(-1, 0, _intervals);
};

function _eraseOverlapIntervals(prev, curr, _intervals) {
  // 检查是否所有 interval 处理完，若处理完，则表明不用删除，返回 0;
  if (curr === _intervals.length) {
    return 0;
  }

  // 定义变量 taken 记录：如果保留当前区间，需要删除多少其他区间
  // 定义变量 nottaken 记录：如果删除当前区间，最少需要删除多少区间
  let taken = Infinity;
  let nottaken;

  if (prev === -1 || _intervals[prev][1] <= _intervals[curr][0]) {
    // 只有没有发生重叠时，才可以选择保留当前区间
    taken = _eraseOverlapIntervals(curr, curr + 1, _intervals);
  }

  // 其他情况，可以考虑删除当前区间，看看删除之后，会不会产生最好结果
  nottaken = _eraseOverlapIntervals(prev, curr + 1, _intervals) + 1;

  return Math.min(taken, nottaken)
};

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var eraseOverlapIntervals = function(intervals) {
  if (intervals.length <= 1) {
    return 0;
  }

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

  let end = _intervals[0][1], count = 0;

  for(let i = 1; i < _intervals.length; i++) {
    if (_intervals[i][0] < end) {
      // 发生重叠
      count++;
      end = Math.min(end, _intervals[i][1]);
    } else {
      end = _intervals[i][1]
    }
  }

  return count;
};

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var eraseOverlapIntervals = function(intervals) {
  if (intervals.length <= 1) {
    return 0;
  }

  // 区间按照结束时间排序
  let _intervals = intervals.sort((a, b) => a[1] - b[1]);

  let end = _intervals[0][1], count = 1;
  for(let i = 1; i < _intervals.length; i++) {
    if (end <= _intervals[i][0]) {
      // 没有发生重叠
      count++;
      end = _intervals[i][1];
    }
  }

  return intervals.length - count;
};