最大嵌套区间集

3
这是一个基于查找最大嵌套区间集大小的问题。
有许多间隔,每个间隔都由包含起始点和结束点(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)。
我猜这样可能很难理解,但我没有其他选择......如果有人有任何其他算法来解决它......请发布,因为我的算法需要更长时间的实现(涉及到许多数据结构),谢谢!

2
如果你不想写太多代码(根据B-A之间的距离对它们进行排序,然后使用两个循环),就可以使用N^2的时间复杂度。为了获得更好的效率,你需要创建一些数据结构。而你提出的方法则需要花费一个小时来完成加上测试。 - Mark
@IonescuRobert 我不理解你提出的解决方案。你按大小对区间进行排序,然后这两个循环要做什么? - John Kurlak
1个回答

0

编辑:这里发布了一些解决问题的方案here,其中包括两个声称是O(n lg n)的解决方案。然而,我认为O(n lg n)的解决方案不起作用。我在那个页面上发表了评论,说明了原因。如果有人有O(n lg n)的解决方案,我很乐意听取。

二次方解决方案

可以使用动态规划在O(n^2)时间内解决此问题:

  1. 计算每个区间包含多少个区间(可以使用两个嵌套循环完成)
  2. 按包含区间数量升序排序区间
  3. 使用递归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);
        }
    }
}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接