3

これは、ネストされた最大間隔セットのサイズを見つけることに基づく問題です。

開始点と終了点 (si, ei) を含むペアによってそれぞれ定義される多くの間隔があります。i2 が完全に i1 の内側にある場合、2 つの区間 i1 と i2 はネストされていると呼ばれます。例:- (3,4) は (2,6) の一部であるため、(2,6) と (3,4) は入れ子になっています。同様に、k 間隔 i1、i2、i3....ik は、i2 が i1 の内側にあり、i3 が i2 の内側にある、というようにネストされていると呼ばれます。そのセット内のすべての間隔がネストを生成できるように、指定された間隔から間隔の最大セットのサイズを決定します。

私は次のように考えました:- 例を考えてみましょう- (​​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] となるように並べ替える 最初から始めるよりinterval リンクされたリストを開始します..次の間隔が間隔内にある場合、ノードを下に移動し、ノードを下に作成されたグラフをトラバースします（メインリスト以外）..このグラフの最大レベルノードのポインターを保存します新しい間隔が収まる..リンクされたリストをさらにトラバースして、現在の間隔が誰の下にあるかを確認します..最後に、現在の間隔を接続する必要があるノードへのポインターを取得します..これのレベルを比較しますすでに持っている最大レベルのノード.....最大レベルの最終値は、最大のネストされた間隔セットのサイズです..

上記のソリューションの複雑さは次のようになります:- O(n(k+l) + nlogn)

この方法で取得するのは難しいと思いますが、他に選択肢はありません...誰かがそれを解決するための他のアルゴリズムを持っている場合..私のアルゴリズムは実装に時間がかかるため投稿してください(多くのデータ構造が含まれます)。 .. ありがとう！！！

4

1 に答える 1

0

編集: O(n lg n) であると主張する 2 つを含む、問題のいくつかの解決策がここに投稿されています。ただし、 O(n lg n) ソリューションは機能しないと思います。そのページに理由を示すコメントを書きました。誰かが O(n lg n) ソリューションを持っている場合は、ぜひ聞いてください。

二次解

この問題は、動的計画法を使用して O(n^2) 時間で解決できます。

  1. 各間隔に含まれる間隔の数を計算します (2 つのネストされたループで実行できます)
  2. 含まれる間隔の数の昇順で間隔を並べ替えます
  3. 再発MaxNestedIntervalsを使用して問題を解決する

*注: ステップ 1 は、次のソリューションを使用して O(n lg n) 時間で実行できます:ネストされた間隔をカウントするための Sub O(n^2) アルゴリズム? ステップ 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);
        }
    }
}
于 2014-04-24T05:59:52.660 に答える