将区间集合分割为最小的不相交区间集合

Question

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

示例：

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 函数中，我可以利用二分搜索来加速，但我主要想知道：

• 这是一个已知的问题，在算法世界中有一个名称吗？
• 有没有一种最优解决方案与我尝试的方法无关？

- ostrebler

---

你尝试了什么，遇到了什么问题？ - Always Learning

我更新了我的问题并添加了更多细节。 - ostrebler

这是一个非常好的问题。我有时间后会回答。作为提示，我们需要使用不存在的Array.unfold()。但不用担心，这只是一种从种子值创建数组的方法。 - Redu

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

- Matt Timmermans

Answer 2

与Matt的答案类似，这个方案收集所有点，并从中构建输出，保持计数以便检测间隔之间的差距。

不同之处在于，这里的第一阶段排除重复项（基于一个Map），而不是后来过滤它们，最后一阶段以稍微更具函数式编程风格编写：

const disjoint = intervals =>
    [...intervals.reduce((acc, [first, last]) =>
        acc.set(first, (acc.get(first )||0) + 1).set(last+1,(acc.get(last+1)||0) - 1)
    , new Map)]
    .sort((a,b) => a[0]-b[0])
    .reduce(([prev, inside, res], [curr, change]) =>
        [curr, inside+change, (!inside || res.push([prev, curr-1]), res)]
    , [0, 0, []] )
    .pop();

console.log(disjoint([[0,9], [2,12]]));
console.log(disjoint([[0,Infinity],[1,5],[4,6]]));
console.log(disjoint([[0,6],[1,2],[3,6],[6,6],[7,9],[7,8]]));

- trincot

Answer 3

这个问题可以映射到图着色问题，其中每个区间是一个顶点，边连接具有重叠的顶点（区间），颜色表示区间所属的集合。根据图着色问题的定义，两个相连的顶点（两个重叠的区间）不应该有相同的颜色（应该属于不同的集合）。

参见https://en.wikipedia.org/wiki/Graph_coloring

威尔士-鲍威尔算法可用于获得良好的解决方案（不能保证最优）。

参见https://gist.github.com/printminion/a337eeb63ba232084dfc

- Tarik