js算法--合并区间

Dear 丶 2022-12-22 06:19 113阅读 0赞

### 给出一个区间的集合，请合并所有重叠的区间。 ###

输入: \[\[1,3\],\[2,6\],\[8,10\],\[15,18\]\], 1  
输出: \[\[1,6\],\[8,10\],\[15,18\]\]。 2  
解释: 区间 \[1,3\] 和 \[2,6\] 重叠, 将它们合并为 \[1,6\]

### 方法一 合并重叠 ###

#### 思路： ####

从示例入手：\[1, 3\] \[2, 6\] 是否可以合并只要对比 \[1, 3\]的最大值 3，\[2, 6\]的最小值 2，3 >= 2 ，则说明可以合并，否则不能。.\[1, 3\] \[2, 6\] \[8,10\]，从3个来看，如果 \[2, 6\]的最大值6 <= \[8,10\]的最小值 8，则说明\[2, 6\] 不能和 \[8,10\]，因此 \[1, 3\] \[2, 6\] 执行合并操作，\[8,10\] 继续与下一个数组执行步骤一。

#### 详解 ####

1.  对区间进行排序（升序）
2.  从第一区间起取当前拟合并区间为a，
3.  取下一区间为b（如果没有b了则输出a，退出）
4.  如果a的尾 > b 的头 ,则合并为 a，否则输出a，把b作为a

#### 代码 ####

function getMerge(arr) { 
        arr.sort((a, b) => { 
            if(a[0] !== b[0]){ 
                return a[0] - b[0]
            }
            return a[1] - b[1]
        })
        let len = arr.length, ans = [],start, end; // 遍历当前区间的最小值与最大值
        for(let i = 0; i < len; i++){ 
            let s = arr[i][0];
            let e = arr[i][1];
            if(start === undefined){ 
                start = s;
                end = e;
            }
            else if(s <= end){ 
                end = Math.max(e, end)
            }
            else{ 
                let part = [start, end];
                ans.push(part);
                start = s;
                end = e;
            }
        }
    
        if (start !== undefined) { 
            let part = [start, end];
            ans.push(part);
        }
        return ans;
    }

### 方案2 合并重叠 ###

#### 详解 ####

1.  对区间进行排序（升序）
2.  定义一个新的数组，用于存储新的数组区间。
3.  从第二个值开始遍历原数组，比较当前区间的最小值是否大于新数组最后一个区间的最大值，如果满足则push进入新的数组；又或者比较当前区间的最大值是否大于新新数组的随后一个区间的最大值，若满足则将新数组的最后一个区间的最大值替换成当前区间的最大值。

#### 代码 ####

function getMerge(arr) {  
        if (!arr || arr.length === 0) {  
            return []; 
        } 
        let input = arr.sort((a, b) => a[0] - b[0]); 
        let res = []; 
        res.push(input[0]);
        for(let i = 1, len = input.length; i < len; i++) {  
            if (input[i][0] > res[res.length - 1][1]) {  
                res.push(input[i]); 
            } else if (input[i][1] > res[res.length - 1][1]){  
                res[res.length - 1][1] = input[i][1]; 
            } 
        } 
        return res; 
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，113人围观）

还没有评论，来说两句吧...

相关阅读

相关一、基础算法9：区间合并模板题+算法模板（区间合并）

文章目录算法模板离散化题目模板模板题区间和原题链接题目题

傷城~/ 2023年10月09日 23:51/ 0 赞/ 9 阅读

相关区间合并 AcWing 803. 区间合并

区间合并 AcWing 803. 区间合并原题链接 [AcWing 803. 区间合并][AcWing 803.] 算法标签区间合并贪心思路

古城微笑少年丶/ 2023年09月28日 11:32/ 0 赞/ 125 阅读

相关区间合并算法

EXCEL 区间值怎么算？ =VLOOKUP(A1,\{0,2;1.01,2.8;1.51,3.3;2.01,3.8;2.51,4\},2) 如图所示：更多追问追答

落日映苍穹つ/ 2023年09月25日 08:53/ 0 赞/ 53 阅读

相关 56. 合并区间（JS实现）

1 题目 > 给出一个区间的集合，请合并所有重叠的区间。 > 示例 1: > 输入: \[\[1,3\],\[2,6\],\[8,10\],\[15,18\]\]

太过爱你忘了你带给我的痛/ 2023年02月17日 03:26/ 0 赞/ 4 阅读

相关 js算法--前 K 个高频元素、寻找峰值和合并区间

前 K 个高频元素给定一个非空的整数数组，返回其中出现频率前 k 高的元素。示例 1: 输入: nums = \[1,1,1,2,2,3\], k = 2

た入场券/ 2022年12月23日 06:42/ 0 赞/ 133 阅读

相关 js算法--合并区间

给出一个区间的集合，请合并所有重叠的区间。输入: \[\[1,3\],\[2,6\],\[8,10\],\[15,18\]\], 1 输出: \[\[1,6\],\

Dear 丶/ 2022年12月22日 06:19/ 0 赞/ 114 阅读

相关（js）leetcode 56. 合并区间

题目： > 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals\[i\] = \[starti, endi\] 。请你合并所有重叠的区间

绝地灬酷狼/ 2022年11月09日 14:20/ 0 赞/ 189 阅读

相关区间合并算法

算法:st,ed表示当前区间的左端点和右端点 1.将所有区间按左端点排序 2.扫描整个区间,扫描的过程中,将所有可能有交集的区间合并 (1)a区间在当前区间的内部:st和

港控/mmm°/ 2022年10月27日 01:40/ 0 赞/ 151 阅读

相关合并区间

题目描述给出一个区间的集合，请合并所有重叠的区间。示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6

傷城~/ 2022年01月22日 00:53/ 0 赞/ 289 阅读

相关 LeetCode：合并区间

给出一个区间的集合，请合并所有重叠的区间。 > 来源：力扣（LeetCode）链接：[https://leetcode-cn.com/problems/merge-inte

梦里梦外;/ 2021年11月16日 14:24/ 0 赞/ 345 阅读