我正在尝试将间隔列表划分为不重叠的子间隔。例如，如果我的输入是
[1,5],[4,9],[6,12],[11,17]
我希望输出是
[1,4], [4,5], [5,6], [6,9], [9,11], [11,12], [12,17]
我希望输出是一个间隔列表，它与原始间隔列表具有相同的联合，但是多个不同子间隔的每个重叠子间隔都被制成不同的间隔。
我的第一个想法是我应该按它们的第一个元素对所有间隔进行排序，如果有重叠，我应该创建一个新的间隔，但是我在让它工作时遇到了一些麻烦。这在本质上似乎与许多间隔问题不同，所以任何建议都会很棒！
对原始区间端点进行排序。然后，每对连续的端点都会在输出中定义一个区间，除非该区间不包含在原始区间的联合中。要确定某个区间是否包含在原始区间的联合中，请从左到右处理端点，并计算当前有多少原始区间与两个端点之间的区间重叠。当遇到原始区间的左端点时，将计数加 1，当遇到原始区间的右端点时，将计数减 1。如果计数大于 0，则当前两个端点之间的间隔应该包含在您的输出中，否则不包含。
我不确定，如果我理解正确，但只要间隔列表中没有漏洞，以下应该有效：
列出区间的所有端点
1, 5, 4, 9, 6, 12, 11, 17
对该列表进行排序
1, 4, 5, 6, 9, 11, 12, 17
通过始终使用相邻数字作为新间隔的端点来创建新间隔
[1,4] [4,5] [5,6] [6,9] [9,11] [11,12] [12,17]
如果您的间隔列表有一些漏洞，您必须检查每个新创建的间隔是否与源间隔之一重叠。
受@user2566092 的回答启发，我想出了一种不同的方法。
首先，这是一个带有“洞”的示例：
[1.3]
[6..9]
[8...12]
这应该导致：
[1.3]
[6,8]
[8,9]
[9..12]
为此，首先确定一组唯一端点并对其进行排序：
1, 3, 6, 8, 9, 12
然后遍历由连续对形成的所有可能的子区间 AB：
[1,3]
[3,6]
[6,8]
[8,9]
[9,12]
对于每个区间 AB 尝试找到与 AB 相交的原始区间 XY。如果出现这种情况：
(B > X) && (Y > A)
例如：
[A=1, B=3] is included because of [X=1, Y=3]
[A=3, B=6] is excluded, interval [X=1, Y=3] is excluded because Y=A,
the other original intervals are excluded because B<X
编辑：这是一个 Java 实现。
import java.util.*;
public class Main {
public static void main(final String[] args) {
determineSubIntervals(new Interval[] { new Interval(1, 5), new Interval(4, 9), new Interval(6, 12), new Interval(11, 17) });
determineSubIntervals(new Interval[] { new Interval(1, 3), new Interval(6, 9), new Interval(8, 12) });
}
private static List<Interval> determineSubIntervals(final Interval[] originals) {
System.out.println("Originals: " + Arrays.toString(originals));
final Set<Integer> endpoints = extractOrderedUniqueEndpoints(originals);
final List<Interval> candidates = createConsecutiveIntervals(endpoints);
final List<Interval> subIntervals = removeDisjunct(candidates, originals);
System.out.println("Sub intervals: " + subIntervals);
return subIntervals;
}
private static Set<Integer> extractOrderedUniqueEndpoints(final Interval[] intervals) {
final Set<Integer> endpoints = new TreeSet<Integer>();
for (final Interval interval : intervals) {
endpoints.add(interval.getStart());
endpoints.add(interval.getEnd());
}
return endpoints;
}
private static List<Interval> createConsecutiveIntervals(final Set<Integer> endpoints) {
final List<Interval> intervals = new ArrayList<Interval>();
final Iterator<Integer> it = endpoints.iterator();
Integer start = null;
while (it.hasNext()) {
final Integer end = it.next();
if (start != null) {
final Interval candidate = new Interval(start, end);
intervals.add(candidate);
}
start = end;
}
return intervals;
}
private static List<Interval> removeDisjunct(final List<Interval> candidates, final Interval[] intervals) {
final Iterator<Interval> it = candidates.iterator();
while (it.hasNext()) {
final Interval candidate = it.next();
if (isDisjunct(candidate, intervals)) {
it.remove();
}
}
return candidates;
}
private static boolean isDisjunct(final Interval candidate, final Interval[] intervals) {
final int a = candidate.getStart();
final int b = candidate.getEnd();
for (final Interval interval : intervals) {
final int x = interval.getStart();
final int y = interval.getEnd();
if ((b > x) && (y > a)) {
return false;
}
}
return true;
}
}
间隔类：
public class Interval {
private final int start;
private final int end;
public Interval(final int start, final int end) {
this.start = start;
this.end = end;
}
public int getStart() {
return start;
}
public int getEnd() {
return end;
}
@Override
public String toString() {
return String.format("[%s,%s]", start, end);
}
}
输出：
Originals: [[1,5], [4,9], [6,12], [11,17]]
Sub intervals: [[1,4], [4,5], [5,6], [6,9], [9,11], [11,12], [12,17]]
Originals: [[1,3], [6,9], [8,12]]
Sub intervals: [[1,3], [6,8], [8,9], [9,12]]
下图展示了我们的输入和所需的输出。我们有 5 个间隔（我在原来的基础上添加了一个，以覆盖孔的情况）。
我们希望将这些区间（标记为 1..5）分解为不重叠的子区间（标记为 A..I）。因此，例如区间 1[1,5]可以分解为子区间 A[1,4]和 B [4,5]。
首先我们设置数据。然后我们获取唯一的端点并对它们进行排序，从相邻的数字中创建新的区间。
# setup data and start decomposition
input <- c(1,5,4,9,6,12,11,17, 18,20)
intervals <- data.table(matrix(input,ncol=2,byrow=TRUE))
endpoints <- sort(unique(input))
decomp <- data.table(matrix(c(head(endpoints, -1), endpoints[-1]), ncol=2))
最后，我们需要将这些新的子区间加入到原始区间中。这可以用来排除空洞，也可以用来识别需要哪些子区间来构建哪些主区间。在这里，使用了基于二分搜索的区间连接（foverlaps）。
# align decomposition to segs
intervals[, intid := seq_len(length(input)/2)]
decomp[, subid := LETTERS[seq_len(length(endpoints)-1)]]
setkeyv(decomp, c('V1','V2'))
setkeyv(intervals, c('V1','V2'))
relations <- foverlaps(decomp, intervals, type='within', nomatch=0)
从多对多关系表中，我们可以看到哪些区间 id (intid) 与哪些子区间 id (subid) 匹配。例如，intid 1 与 subid A 和 subid B 匹配。请注意，此表中不存在子间隔 H，因为它是一个孔。
> relations
V1 V2 intid i.V1 i.V2 subid
1: 1 5 1 1 4 A
2: 1 5 1 4 5 B
3: 4 9 2 4 5 B
4: 4 9 2 5 6 C
5: 4 9 2 6 9 D
6: 6 12 3 6 9 D
7: 6 12 3 9 11 E
8: 6 12 3 11 12 F
9: 11 17 4 11 12 F
10: 11 17 4 12 17 G
11: 18 20 5 18 20 I
注意，我使用的是multiplot 函数。
# problem
p1 <- ggplot(intervals, aes(x=V1,xend=V2,y=intid,yend=intid))+geom_segment()+geom_vline(xintercept=endpoints, linetype=3)+xlab('')+ylab('')+ggtitle('Input')
# solution
p2 <- ggplot(relations)+
geom_segment(aes(x=i.V1, xend=i.V2, y=intid,yend=intid, color=as.factor(subid)))+
geom_vline(xintercept=endpoints, linetype=3)+
geom_text(aes(x=(i.V1+i.V2)/2, y=intid+0.2, label=subid), color='black')+
geom_segment(data=decomp, aes(x=V1, xend=V2, y=0, yend=0, color=as.factor(subid)))+
geom_text(data=decomp, aes(x=(V1+V2)/2, y=0+0.2, label=subid), color='black')+
geom_hline(yintercept=0.5)+guides(color='none')+xlab('')+ylab('')+ggtitle('Output')
multiplot(p1,p2)