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&nbsp;arr&nbsp;=[ &nbsp;&nbsp;&nbsp;&nbsp;[0,&nbsp;0],//起 &nbsp;&nbsp;&nbsp;&nbsp;[500,&nbsp;1000], &nbsp;&nbsp;&nbsp;&nbsp;[3000,&nbsp;3500],&nbsp;//相同1 &nbsp;&nbsp;&nbsp;&nbsp;[6000,&nbsp;10000],//相同2 &nbsp;&nbsp;&nbsp;&nbsp;[3500,&nbsp;5000],//相同1 &nbsp;&nbsp;&nbsp;&nbsp;[10000,&nbsp;20000],//相同2 &nbsp;&nbsp;&nbsp;&nbsp;[50000,&nbsp;80000]//止] arr.sort((a,b)=>a[0]&nbsp;-&nbsp;b[0])let&nbsp;point&nbsp;=&nbsp;0;let&nbsp;res&nbsp;=&nbsp;[];for&nbsp;(let&nbsp;index&nbsp;=&nbsp;0;&nbsp;index&nbsp;<&nbsp;arr.length;&nbsp;index++)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;if(point&nbsp;<&nbsp;arr[index][0]){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res.push([point,arr[index][0]]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;point&nbsp;=&nbsp;arr[index][1] &nbsp;&nbsp;&nbsp;&nbsp;}else{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;point&nbsp;=&nbsp;Math.max(point,arr[index][1]) &nbsp;&nbsp;&nbsp;&nbsp;} } console.log(res)楼上说的对，时间复杂度取决于排序

Answer 2

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