如何将间隔集(输入集)有效地分成最小的不相交间隔集(输出集),以使输入集的所有间隔都可以表示为输出集的间隔的并集?
例子 :
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 ] ]