N37合并区间

题目链接：https://www.nowcoder.com/share/jump/8109288801719904170940

题目要求：给出一组区间，请合并所有重叠的区间。

请保证合并后的区间按区间起点升序排列。

数据范围：区间组数 0≤𝑛≤2×1050≤n≤2×105，区间内 的值都满足 0≤𝑣𝑎𝑙≤2×1050≤val≤2×105

要求：空间复杂度 𝑂(𝑛)O(n)，时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)O(nlogn)

进阶：空间复杂度 𝑂(𝑣𝑎𝑙)O(val)，时间复杂度𝑂(𝑣𝑎𝑙)O(val)

样例：输入：[[10,30],[20,60],[80,100],[150,180]]

输出：[[10,60],[80,100],[150,180]]

因为编辑器一直报错所以本地写了

/**解题思路：
 * 第一步：把数组按照每个区间的起点从小到大排序；
 * 第二步：定义一个空数组resultArr接收合并后的区间
 * 第三步：遍历第一步中的数组，如果resultArr为空或者元素的起点大于resultArr最后一个元素的末点，则加入到resultArr中
 * 第四步：不满足第三步的元素，代表元素的起点小于resultArr中最后一个元素的末点，证明区间重叠，则需要把resultArr中最后一个元素的末点替换成（新元素区间末点和resultArr中最后一个元素的末点中大的那位）
 */
 function mergeArray(intervals: Array<Array<number>>) {
  if (intervals.length === 0) {
    return [];
  } else {
    intervals.sort((a, b) => {
      return a[0] - b[0];
    });
    const resultArr: Array<Array<number>> = [];
    intervals.forEach((item) => {
      if (resultArr.length === 0 || item[0] > resultArr[resultArr.length - 1][1]) {
        resultArr.push(item);
      } else {
        resultArr[resultArr.length - 1][1] = Math.max(Number(item[1]), Number(resultArr[resultArr.length - 1][1]));
      }
    });
    return resultArr;
  }
}
//参数在规定形式内可以传任意区间
mergeArray([[10,30],[20,60],[80,100],[150,180]]);