编辑:这里发布了一些解决问题的方案here,其中包括两个声称是O(n lg n)的解决方案。然而,我认为O(n lg n)的解决方案不起作用。我在那个页面上发表了评论,说明了原因。如果有人有O(n lg n)的解决方案,我很乐意听取。
二次方解决方案
可以使用动态规划在O(n^2)时间内解决此问题:
- 计算每个区间包含多少个区间(可以使用两个嵌套循环完成)
- 按包含区间数量升序排序区间
- 使用递归
MaxNestedIntervals
来解决问题
*注意:
第1步可以使用此处的解决方案在O(n lg n)时间内完成:Sub O(n^2) algorithm for counting nested intervals?
第2步可以使用任何最优比较排序算法在O(n lg n)时间内完成。
可能有一种方法可以优化第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);
}
}
}