algorithm - 非優勢ペアを見つけるアルゴリズム

Question

整数のペアが与えられます(a1,b1),...,(an,bn)。と の場合、ペアはペアiによって「支配」されます。他のどのペアにも支配されていないペアのリストをすばやく決定するアルゴリズムは何ですか?jai < ajbi < bj

すべてのペアを確認できます。各ペアについて、すべてのペアをもう一度調べて、他のペアによって支配されているかどうかを確認します。このアルゴリズムは ordern^2です。n順序またはのアルゴリズムはありn log nますか?

Answer 1

非支配ペアをO(n log n)時間内に見つけることができます。

の降順でペアを並べ替えてから、ペアa_iを反復処理します。bまた、これまでに見られた最大値を追跡しb_maxます。各ステップで、次の(a_i,b_i) ペアのb値が より大きい場合はb_max、それを回答リストに追加して更新しb_maxます。最終的な回答リストは、非支配ペアになります。

a 正しさ: あるペアがより大きな値とより大きな を持つ場合にのみ、ペアは支配的ですb。ペアを検討するとき、その値をより大きな のペアの中でb最大値と正確に比較しているので、ペアが優勢でない場合にのみペアをリストに追加します。ba

ランタイム: ペアを値でソートするには時間がかかりますO(n log n)。反復にはO(n)時間がかかるため、全体の実行時間はO(n log n).

Answer 2

私が正しく理解している場合、支配されていないペアは、a または b がそれぞれ a および b の最大値以上であるペアです。

したがって、a と b の両方の最大値 (ループ O(n) の a) を見つけてから、別のループを実行して、上記の条件を満たすカップルを見つけるだけです。要約すると、O(n) 時間の複雑さです。

「支配されていない」ペアのインデックスの ArrayList を返す Java の小さな例:

    ArrayList<Integer>findUndominatedPairIndexes(int[][]arrayOfPairs)
    {
        ArrayList<Integer>result=new ArrayList<Integer>();
        int maxX=Integer.MIN_VALUE;
        int maxY=Integer.MIN_VALUE;
        int i=arrayOfPairs.length;
        /**
         * get the max value
         */
        for(;--i>=0;)
        {
            int x=arrayOfPairs[i][0];
            int y=arrayOfPairs[i][1];
            if (x>maxX)
            {
                maxX=x;
            }
            if (y>maxY)
            {
                maxY=y;
            }
        }
        for(i=arrayOfPairs.length;--i>=0;)
        {
            int[] pair=arrayOfPairs[i];
            if (pair[0]>=maxX||pair[1]>=maxY)
            {
                result.add(new Integer(i));
            }

        }
        return result;
    }