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

本文介绍了将间隔集拆分为最小的不相交间隔集的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我如何有效地将一组间隔( input 集合)拆分为最小的不相交间隔( output 集合)，以使所有输入集的间隔可以表示为输出集的间隔的并集?

How can I efficiently split a set of intervals (the input set) into a minimal set of disjoint intervals (the output set), in such a way that all intervals from the input set can be expressed as unions of intervals from the output set ?

示例:

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]

我需要用Java语言执行此操作.这是我尝试过的想法:

I need to do this in Javascript. Here is the idea I tried :

// 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函数中，我可以进行二进制搜索以加快速度，但是我主要想知道是否:

But it is very inefficient. In the pos function, I could do a binary search to speed things up, but I mainly wonder if :

• 这是一个已知的问题，在算法世界中有个名字
• 有一个最佳解决方案，与我尝试过的无关

推荐答案

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

Every boundary point in the input set also needs to be in the output set. The interval between each adjacent pair of boundary points is in the output if it's inside at least one input.

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