javascript - 将一组区间拆分为一组最小的不相交区间
问题描述
如何有效地将一组间隔(输入集)拆分为最小的不相交间隔集(输出集),使得输入集中的所有间隔都可以表示为输出集中的间隔联合?
例子 :
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 ] ]
推荐阅读
- php - 如何防止在 PHP 中下载 MP3 文件?
- angular - 传递模块导入语句
- r - 带有 R 中日期的 if 语句 - 每年概括
- java - 实现方法 org.postgresql.jdbc4.Jdbc4Connection.getSchema()
- objective-c - Objective-C 和 Swift 用户想要的功能之间的区别?
- spring-boot - spring data arangodb - 没有可用的 MappingContext,创建名称为“resourceMappings”的 bean 时出错
- javascript - 嵌套反对迭代Javascript
- java - Java 11 / IntelliJ:找不到模块
- java - Camel REST DSL 招摇输出包含无效的 responseSchema 元素
- android - 签名的APK文件上传失败