「算法学习」：区间合并，多区间重合合并

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

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

算法思想：首先对区间数组依照左闭合区间数的大小进行排序，此时我们以第一个区间作为基准区间进行贪心算法的merge，遍历数组比较，因为区间数组是经过排序的，这个适合如果基准数组的右闭合数比当前比较的左闭合数要大，则肯定存在区间重合，此时比较双方右闭合数大小，取最大数作为基准区间的右闭合数。然后继续比较merge，直到没有区间重合推入栈中，最后返回的结果数组则为最大的区间数组

/*** @param {number[][]} intervals* @return {number[][]}*/
var merge = function (intervals) {let res = [];intervals.sort((a, b) => a[0] - b[0]); // 先按区间的开始处进行排序let prev = intervals[0];//选择第一个区间作为基准比较//遍历数组，对比区间范围，因为选择了第一个区间为基准数组，则从第二个区间比较开始for (let i = 1; i < intervals.length; i++) {let cur = intervals[i];//当前区间/*开始时已经对按照区间的左开始数的大小进行了排序，当基准区间的右闭合数大于遍历的左开始数时候说明有重合*/if (prev[1] >= cur[0]) {//如果区间重合，在基准区间和当前区间中选择右闭合数大的一个prev[1] = Math.max(cur[1], prev[1]); } else {//如果基准区间右闭合数没有当前的左开始数大，则不存在重合，推进栈中       res.push(prev);// 更新 prevprev = cur;  }}// 最后一次赋值，也要 push 一下res.push(prev);return res;
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！