请教一个算法问题?

Question

请教一个算法问题

输入原数组(按start排序, 并且下一项的start一定>=前一项的end)

[
    { "start": 1, "end": 2, "content": [ "A", "B", "E" ] },    //0
    { "start": 2, "end": 3, "content": [ "B", "C" ] },        //1
    { "start": 3, "end": 4, "content": [ "B", "D" ] },        //2
    { "start": 4, "end": 5, "content": [ "D" ] },            //3
    { "start": 7, "end": 8, "content": [ "B" ] },            //4
    { "start": 9, "end": 11, "content": [ "B", "C" ] }        //5
]

提取出连续的相同项合并成一个新的对象, 插入原数组, 根据start和end判断是否连续
如例子里的(0,1,2)项里的B 提取并合并得到{ "start": 1, "end": 4, "content": ["B"] }
(2,3)项里的D 提取并合并得到{ "start": 3, "end": 5, "content": ["D"] }
插入原数组后再按start, end 排序

提取后, (3)项会变为{ "start": 4, "end": 5, "content": [ ] }
content长度为0, 需要移除

最后输出

[
    { "start": 1, "end": 2, "content": [ "A", "E" ] },
    { "start": 1, "end": 4, "content": [ "B" ] },
    { "start": 2, "end": 3, "content": [ "C" ] },
    { "start": 3, "end": 5, "content": [ "D" ] },
    { "start": 7, "end": 8, "content": [ "B" ] },
    { "start": 9, "end": 11, "content": [ "B", "C" ] }
]

Answer 1

let arr = [
    { "start": 1, "end": 2, "content": [ "A", "B", "E" ] },    //0
    { "start": 2, "end": 3, "content": [ "B", "C" ] },        //1
    { "start": 3, "end": 4, "content": [ "B", "D" ] },        //2
    { "start": 4, "end": 5, "content": [ "D" ] },            //3
    { "start": 7, "end": 8, "content": [ "B" ] },            //4
    { "start": 9, "end": 11, "content": [ "B", "C" ] }        //5
]

let obj = {}
let list = arr.reduce((list, item, index, arr) => {
    item.content.forEach(citem => {
        let i = index
        let next, cindex
        while ((next = arr[i + 1]) && arr[i].end === next.start && (cindex = next.content.indexOf(citem)) >= 0) {
            i++
            next.content.splice(cindex, 1)
        }
        let end = arr[i].end
        let key = item.start + '-' + end
        if(!obj[key]){
            list.push(obj[key] = {
                start: item.start,
                end,
                content: [citem]
            })
        }else{
            obj[key].content.push(citem)
        }
    })
    return list
}, [])

console.log(list)

Answer 2

function merge(data) {
    let obj1 = {}, obj2 = {};

    for (let {start, end, content: arr} of data)
        for (let key of arr)
            (obj1[end] ??= {})[key] = [obj1[start]?.[key]?.pop() ?? start];

    for (let [end, arr] of Object.entries(obj1))
        for (let key in arr)
            for (let start of arr[key])
                (obj2[`${start},${end}`] ??= {start, end: +end, content: []}).content.push(key);

    return Object.values(obj2).sort((a, b) => a.start - b.start || a.end - b.end);
}

Answer 3

function mergeSameItems(arr) {
    let i = 0;
    while (i < arr.length - 1) {
        for (let j = 0; j < arr[i].content.length; j++) {
            let item = arr[i].content[j];
            if (arr[i + 1].content.includes(item)) {
                arr.push({
                    'start': arr[i].start,
                    'end': arr[i + 1].end,
                    'content': [item]
                });
                arr[i].content = arr[i].content.filter(x => x !== item);
                arr[i + 1].content = arr[i + 1].content.filter(x => x !== item);
            }
        }
        if (arr[i].content.length === 0) {
            arr.splice(i, 1);
        } else {
            i += 1;
        }
    }
    arr.sort((a, b) => a.start - b.start || a.end - b.end);
    return arr;
}