求助一道设计算法的题，想不出来怎么实现？这个怎么用代码写？

Question

写一个merge函数

[
    { start: 1, end: 2 },
        { start: 2, end: 3 },
        { start: 5, end: 6 },
        { start: 3, end: 5 },
        { start: 8, end: 9 },
        
    
]

参数是一个数组

如果参数只有{ start: 1, end: 2 },
{ start: 2, end: 3 } 合并成 { start: 1, end: 3 } 然后返回数组 [{ start: 1, end: 3 }]

如果参数{ start: 1, end: 2 },
{ start: 2, end: 3 } { start: 5, end: 6 }

此时返回数组 [{ start: 1, end: 3 }, { start: 5, end: 6 }]

如果参数是

[
    { start: 1, end: 2 },
        { start: 2, end: 3 },
        { start: 5, end: 6 },
        { start: 3, end: 5 },
        { start: 8, end: 9 },

        { start: 11, end: 15 },

    ]

返回 [{ start: 1, end: 6 }, { start: 8, end: 9 },{ start: 11, end: 15 }]

Answer 1

说一下拍脑袋想到最好理解的思路,肯定有更优解.
定义一个数组.
let mark = [0,0,0,0....0]

初始长度是未定的.
开始遍历传入数组,假如第一个对象是s1e5,先把mark补齐到5位,再把mark的第1个到第5位置改为1.变成
[1,1,1,1,1,...,0]
以此类推
最后得到的mark数组是0和1构成的array.
判断这个array上连续的1出现的起始和结束的位置,组成结果集就可以了.

Answer 2

leetcode 差不多有原题，地址

代码 https://github.com/hanzichi/l... 可以参考下

Answer 3

最简单的做法就是先将数组里的每个对象按照 start 从小到大 排序， 然后遍历处理是否要合并

Answer 4

let arr = [
    { start: 1, end: 2 },
    { start: 2, end: 3 },
    { start: 5, end: 6 },
    { start: 3, end: 5 },
    { start: 8, end: 9 },
    { start: 11, end: 15 },

]

let res = arr.sort((acc, cur) => acc.start - cur.start).reduce((acc, cur) => {
    if (acc) {
        let last = acc[acc.length - 1];
        if (last.end === cur.start) {
            last.end = cur.end;
        } else {
            acc.push(cur)
        }
        return acc;
    }
    return [cur];
}, null)

Answer 5

let data = [
    { start: 1, end: 2 },
    { start: 2, end: 3 },
    { start: 5, end: 6 },
    { start: 3, end: 5 },
    { start: 8, end: 9 },
    { start: 11, end: 15 }
]
let result = []
data.sort((a,b) => {
    return a.start - b.start
}).map( val => {
    let temp = result[result.length-1]
    result.length && val.start == temp.end ? temp.end = val.end : result.push(val)
    return val
})
console.log(result)

Answer 6

用mark数组的方法如果数据标志比较少还好说，如果有多的，则占用太多空间，肯定不合适
这个问题我觉得合理的解决是递归扫描是否有合并（最好先排序）
大致算法如下

1.先根据start排序各个对象，本轮扫描有合并变量置0

2.然后依次扫描各个对象，看是否有合并，如果有合并则合并对象，本轮扫描有合并指示变量置1

3.判断本轮扫描是否有合并，没有则输出，否则跳到1