如何将间隔集(输入集)有效地分成最小的不相交间隔集(输出集),以使输入集的所有间隔都可以表示为输出集的间隔的并集?

例子 :

Input: [0,9] [2,12]
Output: [0,1] [2,9] [10,12]

Test :
[0,9] = [0,1] ∪ [2,9]
[2,12] = [2,9] ∪ [10,12]

Input: [0,Infinity] [1,5] [4,6]
Output: [0,0] [1,3] [4,5] [6,6] [7,Infinity]

Test :
[0,Infinity] = [0,0] ∪ [1,3] ∪ [4,5] ∪ [6,6] ∪ [7,Infinity]
[1,5] = [1,3] ∪ [4,5]
[4,6] = [4,5] ∪ [6,6]

我需要用Javascript来做。这是我尝试过的想法:
// The input is an array of intervals, like [[0,9], [2,12]], same for the output

// This function converts a set of overlapping
// intervals into a set of disjoint intervals...
const disjoin = intervals => {
  if(intervals.length < 2)
    return intervals
  const [first, ...rest] = intervals
  // ...by recursively injecting each interval into
  // an ordered set of disjoint intervals
  return insert(first, disjoin(rest))
}

// This function inserts an interval [a,b] into
// an ordered set of disjoint intervals
const insert = ([a, b], intervals) => {
  // First we "locate" a and b relative to the interval
  // set (before, after, or index of the interval within the set
  const pa = pos(a, intervals)
  const pb = pos(b, intervals)

  // Then we bruteforce all possibilities
  if(pa === 'before' && pb === 'before')
    return [[a, b], ...intervals]
  if(pa === 'before' && pb === 'after')
    // ...
  if(pa === 'before' && typeof pb === 'number')
    // ...
  // ... all 6 possibilities
}

const first = intervals => intervals[0][0]
const last = intervals => intervals[intervals.length-1][1]

const pos = (n, intervals) => {
  if(n < first(intervals))
    return 'before'
  if(n > last(intervals))
    return 'after'
  return intervals.findIndex(([a, b]) => a <= n && n <= b)
}

但这是非常低效的。在pos函数中,我可以执行二进制搜索来加快速度,但是我主要想知道是否:
  • 这是一个已知问题,在算法世界中有一个名字
  • 有一个最佳解决方案,它与我尝试过的
  • 无关

    最佳答案

    输入集中的每个边界点也都必须位于输出集中。如果相邻边界点对之间的间隔至少在一个输入中,则该间隔在输出中。

    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 ] ]
    

    09-11 19:15
    查看更多