力扣刷题：合并区间

题目：
以数组intervals表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 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：

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

解析:
这是一道典型的贪心算法题目：

• 局部最优选择：每次只考虑当前区间与前一个合并区间的关系

• 无后效性：一旦区间被合并，就不会再重新考虑

• 一次遍历：不需要回溯

具体代码：

/** * @param {number[][]} intervals * @return {number[][]} */varmerge=function(intervals){intervals.sort((a,b)=>a[0]-b[0])// 步骤1：排序（预处理）letres=[intervals[0]]// 步骤2：初始选择第一个区间for(leti=1;i<intervals.length;i++){letcur=intervals[i]// 贪心决策：能合并就合并，不能合并就新增if(cur[0]<=res[res.length-1][1]){// 如果当前区间与最后一个合并区间重叠// 贪心扩展：合并到已有区间（局部最优扩展）res[res.length-1][1]=Math.max(res[res.length-1][1],cur[1])}else{// 贪心新建：不能合并就新建区间res.push(intervals[i])}}returnres};