这是一个基于查找最大嵌套区间集大小的问题..
有许多间隔,每个间隔由包含起点和终点 (si, ei) 的对定义。如果 i2 完全位于 i1 内部,则两个区间 i1 和 i2 称为嵌套。示例:- (2,6) 和 (3,4) 是嵌套的,因为 (3,4) 是 (2,6) 的一部分。类似地,如果 i2 位于 i1 内,i3 位于 i2 内,... 等,则 k 间隔 i1、i2、i3....ik 称为嵌套。从给定区间确定最大区间集的大小,以便该集合中的所有区间都可以产生嵌套。
我是这样想的:- 让我们举个例子- (0,7) (0,5) (1,21) (1,9) (2,8) (2,4) (3, 20) (4,16) (5,15) (6,21) 按照a[i-1]<=a[i] && b[i-1]>=b[i] 的方式排序比从第一个间隔开始,我们开始一个链表。如果下一个间隔在一个间隔内,我们向下移动节点并遍历沿着节点创建的图(主列表除外)。我们将最大级别节点的指针存储在新间隔可以适合的这张图..并在链表中进一步遍历以查看当前间隔来自谁..最后我们有一个指向我们必须附加当前间隔的节点的指针..并比较这个节点的级别与我们已经拥有的最大级别.....最大级别的最终值是最大嵌套间隔集的大小..
上述解决方案的复杂性可能是:- O(n(k+l) + nlogn)
我想这样很难得到它,但我别无选择...如果有人有任何其他算法来解决它..请发帖,因为我的算法将花费更长的时间来实现(很多数据结构涉及)...谢谢!!!
最佳答案
编辑:问题的一些解决方案已发布 here ,包括两个声称是 O(n lg n)。但是,我认为 O(n lg n) 解决方案不起作用。我在该页面上发表了评论,说明了原因。如果有人有 O(n lg n) 的解决方案,我很想听听。
二次解
这个问题可以用动态规划在 O(n^2) 时间内解决:
- 计算每个区间包含多少个区间(可以用两个嵌套循环来完成)
- 按包含区间数的升序对区间进行排序
- 使用递归
MaxNestedIntervals
解决问题
*注: 使用此处的解决方案可以在 O(n lg n) 时间内完成第 1 步:Sub O(n^2) algorithm for counting nested intervals? 使用任何基于比较的最优排序算法都可以在 O(n lg n) 时间内完成步骤 2。 可能有一种方法可以优化第3步,但我还没有找到。
重复发生
MaxNestedIntervals(i) =
max {j = 0 to i-1} :
1 + MaxNestedIntervals(j) if interval i contains interval j
0 if interval i doesn't contain interval j
基本案例
MaxNestedIntervals(i) =
0 if interval i contains 0 intervals
1 if interval i contains 1 interval
示例代码
import java.util.*;
public class MaxNestedIntervals {
public static void main(String[] args) {
Interval[] intervals = new Interval[10];
intervals[0] = new Interval(0, 7);
intervals[1] = new Interval(0, 5);
intervals[2] = new Interval(1, 21);
intervals[3] = new Interval(1, 9);
intervals[4] = new Interval(2, 8);
intervals[5] = new Interval(2, 4);
intervals[6] = new Interval(3, 20);
intervals[7] = new Interval(4,16);
intervals[8] = new Interval(5,15);
intervals[9] = new Interval(6,21);
int n = intervals.length;
AugmentedInterval[] augmentedIntervals = new AugmentedInterval[n];
for (int i = 0; i < n; i++) {
augmentedIntervals[i] = new AugmentedInterval(intervals[i]);
}
for (int i = 0; i < n; i++) {
AugmentedInterval outerInterval = augmentedIntervals[i];
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
AugmentedInterval innerInterval = augmentedIntervals[j];
if (outerInterval.contains(innerInterval)) {
outerInterval.numContainedIntervals++;
if (outerInterval.childInterval == null) {
outerInterval.childInterval = innerInterval;
}
}
}
}
Arrays.sort(augmentedIntervals, new Comparator<AugmentedInterval>() {
public int compare(AugmentedInterval i, AugmentedInterval j) {
return i.numContainedIntervals - j.numContainedIntervals;
}
});
int maxNestedIntervals = 0;
AugmentedInterval parentInterval = null;
for (int i = 0; i < n; i++) {
AugmentedInterval currentInterval = augmentedIntervals[i];
if (currentInterval.numContainedIntervals == 0) {
currentInterval.maxNestedIntervals = 0;
} else if (currentInterval.numContainedIntervals == 1) {
currentInterval.maxNestedIntervals = 1;
} else {
int maxNestedIntervalsForCurrentInterval = 0;
for (int j = 0; j < i; j++) {
AugmentedInterval candidateNestedInterval = augmentedIntervals[j];
int maxNestedIntervalsForCurrentCandidate = candidateNestedInterval.maxNestedIntervals + 1;
if (currentInterval.contains(candidateNestedInterval) && maxNestedIntervalsForCurrentCandidate >= maxNestedIntervalsForCurrentInterval) {
maxNestedIntervalsForCurrentInterval = maxNestedIntervalsForCurrentCandidate;
currentInterval.childInterval = candidateNestedInterval;
}
}
currentInterval.maxNestedIntervals = maxNestedIntervalsForCurrentInterval;
if (maxNestedIntervalsForCurrentInterval >= maxNestedIntervals) {
maxNestedIntervals = maxNestedIntervalsForCurrentInterval;
parentInterval = currentInterval;
}
}
}
if (n == 0) {
System.out.println("The largest set of nested intervals is the empty set.");
} else if (maxNestedIntervals == 0) {
System.out.println("The largest set of nested intervals has 1 interval.\n");
System.out.println("That interval is:");
} else {
System.out.println("The largest set of nested intervals has " + (maxNestedIntervals + 1) + " intervals.\n");
System.out.println("Those intervals are:");
}
for (AugmentedInterval currentInterval = parentInterval; currentInterval != null; currentInterval = currentInterval.childInterval) {
System.out.println(currentInterval);
}
System.out.println();
}
private static class Interval implements Comparable<Interval> {
public int start = 0;
public int end = 0;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
public int size() {
return this.end - this.start;
}
public boolean contains(Interval other) {
return (this.start <= other.start && this.end >= other.end);
}
public int compareTo(Interval other) {
return this.size() - other.size();
}
public String toString() {
return "[" + this.start + ", " + this.end + "]";
}
}
private static class AugmentedInterval extends Interval {
public int numContainedIntervals = 0;
public int maxNestedIntervals = 0;
public AugmentedInterval childInterval = null;
public AugmentedInterval(Interval interval) {
super(interval.start, interval.end);
}
}
}
关于algorithm - 最大嵌套区间集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12896156/