js 线段算法 已知完成线段,求剩余线段

Question

例子 已知 起点为0 末点为80000
arr [0] :起点
arr [1] :末点
起点与末点如果相同要求进行合并

最终产生新的剩余段落

以下的数组为完成的线段

       arr =
            [0, 0],//起
            [500, 1000],
            [3000, 3500], //相同1
            [6000, 10000],//相同2
            [3500, 5000],//相同1
            [10000, 20000],//相同2
            [50000, 80000]//止

转换为

            [0, 500],
            [1000, 3000],
            [5000, 6000], 
            [20000, 50000],

Answer 1

var arr =[
    [0, 0],//起
    [500, 1000],
    [3000, 3500], //相同1
    [6000, 10000],//相同2
    [3500, 5000],//相同1
    [10000, 20000],//相同2
    [50000, 80000]//止
]

arr.sort((a,b)=>a[0] - b[0])
let point = 0;
let res = [];
for (let index = 0; index < arr.length; index++) {
    if(point < arr[index][0]){
        res.push([point,arr[index][0]])
        point = arr[index][1]
    }else{
        point = Math.max(point,arr[index][1])
    }
}
console.log(res)

楼上说的对，时间复杂度取决于排序

Answer 2

先按起点排序，然后一趟扫描就能搞定