将间隔集拆分为最小的不相交间隔集

Question

如何有效地将一组间隔（输入集）拆分为最小的不相交间隔集（输出集），以便输入集中的所有间隔都可以表示为输出集中间隔的并集？

\n\n

例子 ：

\n\n

Input: [0,9] [2,12]\nOutput: [0,1] [2,9] [10,12]\n\nTest :\n[0,9] = [0,1] \xe2\x88\xaa [2,9]\n[2,12] = [2,9] \xe2\x88\xaa [10,12]\n\nInput: [0,Infinity] [1,5] [4,6]\nOutput: [0,0] [1,3] [4,5] [6,6] [7,Infinity]\n\nTest :\n[0,Infinity] = [0,0] \xe2\x88\xaa [1,3] \xe2\x88\xaa [4,5] \xe2\x88\xaa [6,6] \xe2\x88\xaa [7,Infinity]\n[1,5] = [1,3] \xe2\x88\xaa [4,5]\n[4,6] = [4,5] \xe2\x88\xaa [6,6]\n

\n\n

我需要在 Javascript 中执行此操作。这是我尝试过的想法：

\n\n

// The input is an array of intervals, like [[0,9], [2,12]], same for the output\n\n// This function converts a set of overlapping\n// intervals into a set of disjoint intervals...\nconst disjoin = intervals => {\n  if(intervals.length < 2)\n    return intervals\n  const [first, ...rest] = intervals\n  // ...by recursively injecting each interval into\n  // an ordered set of disjoint intervals\n  return insert(first, disjoin(rest))\n}\n\n// This function inserts an interval [a,b] into\n// an ordered set of disjoint intervals\nconst insert = ([a, b], intervals) => {\n  // First we "locate" a and b relative to the interval\n  // set (before, after, or index of the interval within the set\n  const pa = pos(a, intervals)\n  const pb = pos(b, intervals)\n\n  // Then we bruteforce all possibilities\n  if(pa === \'before\' && pb === \'before\') \n    return [[a, b], ...intervals]\n  if(pa === \'before\' && pb === \'after\')\n    // ...\n  if(pa === \'before\' && typeof pb === \'number\')\n    // ...\n  // ... all 6 possibilities\n}\n\nconst first = intervals => intervals[0][0]\nconst last = intervals => intervals[intervals.length-1][1]\n\nconst pos = (n, intervals) => {\n  if(n < first(intervals))\n    return \'before\'\n  if(n > last(intervals))\n    return \'after\'\n  return intervals.findIndex(([a, b]) => a <= n && n <= b)\n}\n

\n\n

但这是非常低效的。在pos函数中，我可以进行二分搜索来加快速度，但我主要想知道：

\n\n

\n
• 这是一个已知问题，在算法界有一个名字
\n
• 有一个最优解，与我尝试的无关
\n

\n

Answer 1

输入集中的每个边界点也需要位于输出集中。如果每对相邻边界点之间的间隔位于至少一个输入内部，则该间隔位于输出中。

splitIntervals = (input) => {
    const starts = input.map(x => [x[0],1]);
    const ends = input.map(x => [x[1]+1, -1]);   
    let count=0;
    let prev=null;
    return [...starts, ...ends]
        .sort((a,b) => (a[0] - b[0])) //sort boundary points
        .map(x => {
            //make an interval for every section that is inside any input interval
            const ret= (x[0] > prev && count !== 0 ? [prev, x[0]-1] : null);
            prev=x[0];
            count+=x[1];
            return ret;
        })
        .filter(x => !!x);
}

测试：

> splitIntervals([ [0,9], [2,12] ])
[ [ 0, 1 ], [ 2, 9 ], [ 10, 12 ] ]
> splitIntervals([[0,9], [3,9], [4,13]])
[ [ 0, 2 ], [ 3, 3 ], [ 4, 9 ], [ 10, 13 ] ]