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

Question

例子 已知 起点为0 末点为80000arr [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

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