Day 12： Merge Intervals

看完这题题目
还记得小时候很常被问到：
给你一些数字，请你从这些数中用最少的数，来涵盖最多的范围。於是我们就会拿起笔开画数线。不过今天，我们要用程序码来解题，没有了画笔，我们该如何下手？

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

在解题之前我们先想想要如何在阵列中长得像这样[starti, endi]的元素。只依靠start和end，来决定是否有区间重叠，毕竟我们从画图很容易可以看得出来哪些元素共享哪几个重叠的数，但如果现在我只告诉你头尾两个数，我们是不是需要去比较区间才能知道？

这里我们随意抓出第一和第二个元素也就是[1,3]和[2,6]
我们可以推断：如果第一个元素的 end ≥ 第二个元素的start （3 ≥ 2），就代表有重叠发生

但如果今天的范例长成 intervals = [[8,10],[2,6],[1,3],[15,18]]
我们一样抓出第一和第二个元素也就是 [8,10],[2,6]

依照前面的推断，因为 10 ≥ 6，所以有重叠！？ 完蛋！

也就是说，我们先前可以轻松地抓两个元素来比较是因为：前面的范例恰好每个元素的start是由小到大排列的，也就是说我们应该要确保，每个元素的排列是依照前面的元素大小来排列。

接着再思考一个问题，我们要如何合并多个有重叠的元素，像是我们在原本的范例再多塞一个变成

intervals = [[1,3],[2,6],[5,7],[8,10],[15,18]]
我们应该要把 [1,3],[2,6],[5,7] 合并成 [1,7]

我们可以先把[1,3] 和 [2,6]合并成 [1,6]後，再用[1,6]和[5,7]下去做合并变成[1,7]。
但我们要如何产出[[1,7],[8,10],[15,18]]这个答案？
我们是不是在过程中有一个[1,6]消失了？

也就是说假设我们有一个暂存区空阵列[]，我们把[[1,6]]加入後，往下走到[5,7]，我们应该要拿[5,7]去和暂存区内的[1,6]确认，看看他们有没有需要合并，如果下个元素的start≤前一个暂存区的end，就代表有合并的动作要做。
我们取暂存区的end(6)和下个元素的end(7)，｀取大的当作end｀，直接可以把暂存区这个元素的end替换掉，产生了[1,7]！

那为什麽我们要取大的元素当end，而不直接取後面的？
因为有可能会有[[1,7],[3,6]]这种被涵盖的情况发生。

总结我们要做的事

1. 把元素按照start排序
2. 建立一个空[]放output
3. 一开始直接把第一个元素塞到output
4. 相邻的元素利用是否 前面元素的 end ≥ 後面元素的start，如果有则要做合并，改变end的操作

以上的做法，时间复杂度为Ｏ(nlogn)→主要花在排序，空间复杂度O(n) → 我们的ouput，因为最糟为都没有重叠

最後就是实作程序码。
希望看完上面的解释，希望你也觉得这题根本就跟画数线一样简单拉！

var merge = function (intervals) {
  const sortIntervals = intervals.sort((a, b) => a[0] - b[0]);

  const output = [];
  let current = sortIntervals[0];
  output.push(current);

  for (const next of sortIntervals) {
    const [currentStart, currentEnd] = current;
    const [nextStart, nextEnd] = next;

    if (currentEnd >= nextStart) current[1] = Math.max(currentEnd, nextEnd);
    else {
      current = next;
      output.push(current);
    }
  }
  return output;
};

明日题目预告：Maximum Subarray