2

私は、バイナリ検索が欠落している要素の挿入ポイントを返すという事実をきれいな方法でコーディングする方法を理解しようとしています。

これを、重複しない間隔の最大サブセットを見つけるというアルゴリズムの問​​題に使用します。

私がしていることは、間隔を並べ替えた後、各間隔を維持し、その開始時間が既に選択されている間隔の終了時間と重ならないようにすることです。

線形探索もできますが、ここでは二分探索の方がいいと思いました。私は正しいですか？

したがって、正しいように見えますが、エラーが発生しやすく、API をより適切に使用できる可能性があると思います。

私が行っているのは、最後の間隔でのバイナリ検索であり、前または次と重複するかどうかを確認します (バイナリ検索によって返された挿入ポイントを使用)。

私の論理は正しいですか？また、このアルゴリズムは良い練習になると信じているので、クリーンな Java バージョンを探しています。 

private boolean nonOverlapping(Pair interval, SortedSet<Pair> selectedIntervals) {  
    if(selectedIntervals.isEmpty())  
        return true;  
    if(selectedIntervals.contains(interval)){  
        return true;  
    }       
    Pair[] sortedSelections = selectedIntervals.toArray(new Pair[0]);  
    int pos = Arrays.binarySearch(sortedSelections, interval, new Comparator<Pair>() {  

        @Override  
        public int compare(Pair o1, Pair o2) {  
            return o1.getStart() - o2.getEnd();   
        }  
    });  
    pos = (-pos) -1;  
    if(pos == sortedSelections.length){  
        if(sortedSelections[pos - 1].getEnd() < interval.getStart()){  
            return true;  
        }  

    }           
    else if(sortedSelections[pos].getEnd() > interval.getStart()){  
        if(pos + 1 < sortedSelections.length){  
            if(sortedSelections[pos + 1].getEnd() < interval.getStart()){  
                return false;   
            }   
        }  
        if(pos - 1 >= 0){  
            if(sortedSelections[pos - 1].getEnd() < interval.getStart()){  
                return false;  
            }  
        }  
        return true;  
    }  


    return false;  
}
4

2 に答える 2

3

間隔の範囲の最大の重複しないサブセットを見つける問題は、貪欲なアルゴリズムの古典的なアプリケーションです。標準の貪欲なアルゴリズムは次のとおりです。

  1. すべての間隔を終了時刻で並べ替えます。
  2. すべての間隔を順番に処理する:
    1. 可能な限り早い時間に終了する間隔を追加します。
    2. その間隔と競合するすべての間隔を削除します。
  3. 結果として得られる間隔のセットは、重複しない間隔の最大サブセットです。

このアルゴリズムから、結果のセットに重複する区間が含まれていないことは明らかです。これは、アルゴリズムの各ステップで、競合するすべての区間が将来の考慮から除外されるためです。

これが最適であることを確認するには、交換引数を使用して、より良い解がないことを示します。詳細は、この一連の講義スライドなど、オンラインで確認できます。

お役に立てれば！

于 2013-01-17T20:37:04.503 に答える
0

オーバーラップの「通常の」比較は利用できませんか?

    @Override  
    public int compare(Pair o1, Pair o2) {  
        return o1.getStart() > o2.getEnd() ? 1
            : o1.getEnd() < o2.getStart() ? -1
            : 0;   
    }

説明

これはカバーします

[o2s .. o2e]  [o1s .. o1e]     o1s > o2e  when after  ->  +1
[o1s .. o1e]  [o2s .. o2e]     o1e < o2s  when before ->  -1
otherwise overlap  ->  0

o1s、o1e、o2s、o2e の 4 つの変数すべてが必要です。

于 2013-01-17T21:36:08.543 に答える