---

1、問題

以數組 intervals 表示若干個區間的集合，其中單個區間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區間，并返回 一個不重疊的區間數組，該數組需恰好覆蓋輸入中的所有區間 。

2、示例

示例 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] 可被視為重疊區間。

3、解決方法

（0）方法0——雙指針（錯誤思路）

錯誤思路：把二維數組變為一維數組排序后進行雙指針。雖然這樣用示例一是有效果的，如下圖

let intervals = [[1,3],[2,6],[4,5],[15,18]]
var merge = function(intervals) {let newArray = [];intervals.forEach(item => {newArray.push( ...item)});newArray.sort((a,b)=>{ return a-b}) // 排序// newArray = new Set(...newArray);// console.log('aa', newArray);let left=0,right=1;let arr = []arr.push(newArray[0])while(right < newArray.length) {if(newArray[left] +1 !== newArray[right] && newArray[left] +1 !== newArray[right]) {arr.push(newArray[right])} left++right++}console.log('res', arr);
};
merge(intervals);

將intervals改為[[1,3],[2,6],[4,5],[15,18]]，應該返回 [1,6,15,18]，實際上返回為[1, 15, 18],并不能返回偶數的數據，最后進行兩兩放到一個新數組中

（1）方法1——雙指針（正確）

let intervals = [[2,6],[1,3],[8,10],[15,18]]
var merge = function(intervals) {// 1: 排序：將二維數組的第一項進行排序// 二維數組的第一個相等，就根據第二個排序，不想等就根據第一個排序// 排的是二維數組的第一個，不是二維數組里面每一個數組的第一個第二個排序// 如[[2,6],[1,3],[8,10],[15,18]] 變成[[1,3],[2,6],[8,10],[15,18]]intervals.sort((a,b)=> a[0]== b[0] ? a[1] - b[1]: a[0] - b[0])// 2-1:定義左右指針let left = intervals[0][0],right = intervals[0][1];// 2-2: 定義返回符合條件的空數組let res = []; // 3:遍歷二維數組，獲取每一項進行比較intervals.forEach((item, index) => {debugger// 4： 如果遍歷后的第一個值大于右指針，說明在一個區間，將當前這個區間的左右指針添加到數組中，并將當前item的值設置為左右指針// 如[1,3] 中 1 > 3 不成立，right = 3// [2,6]中 2> 3 不成立 right = 6// [8,10]中 8 > 6 成立 ，將[1,6]添加到數組中，并且左右指針改為當前item的值if(item[0] > right) {res.push([left,right])left = item[0]right = item[1]} else {right = item[1]}});// 5: 遍歷完成后，由于最后區間的值沒有對比，所以額外添加到數組中res.push([left, right])console.log('res', res); // 6: 返回題目效果
};
merge(intervals);

總結

難度： 中等
注意點：使用雙指針解決該問題的時候，不能將二維數組扁平為一維數組進行計算。