6

整数値を持つ間隔のリストがあります[例. [1、4]、[10、19]など]。これらの間隔をいくつかのJavaコレクションのコンテナに入れる方法はありますか[例. コンテナで「ユニオン」関数を呼び出せるように設定します。「ユニオン」関数は、挿入された2つの間隔が重なっている場合、それらが出力にマージされるように、間隔のリストを提供する必要があります。Guava で Range クラスを使用してみましたが、マージする前にすべての間隔を互いに比較することになりました。これに対するエレガントなアプローチは本当にありがたいです! 以下の回答に基づいて私が試したことは次のとおりです。出力は [[1, 15], [17, 20]] で、正しいです。このようなものを実装する既存の API があるかどうかを知りたかったのです。

public static void main(String[] args) {
    // mock data
    List<MyIntRange> rng_lst = new ArrayList<Junk.MyIntRange>();
    rng_lst.add(new MyIntRange(1, 10));
    rng_lst.add(new MyIntRange(5, 15));
    rng_lst.add(new MyIntRange(17, 20));

    // sort intervals by start position
    Collections.sort(rng_lst);

    // merge the intervals which overlap
    List<MyIntRange> res_lst = new ArrayList<Junk.MyIntRange>();
    MyIntRange old_rng = null;
    for (MyIntRange cur_rng : rng_lst) {
        if (old_rng == null) {
            old_rng = cur_rng;
        } else {
            if (old_rng.rng.upperEndpoint() < cur_rng.rng.lowerEndpoint()) {
                // this does not over lap with the next one
                res_lst.add(old_rng);
                old_rng = cur_rng;
            } else {
                // overlap
                old_rng = new MyIntRange(old_rng.rng.lowerEndpoint(),
                        cur_rng.rng.upperEndpoint());
            }
        }
    }
    // add the last range
    res_lst.add(old_rng);

    // done!
    System.out.println(res_lst);
}

// wrapper around Guava's Range to make it comparable based on the
// interval's start
public static class MyIntRange implements Comparable<MyIntRange> {
    Range<Integer> rng;

    public MyIntRange(int start, int end) {
        rng = Ranges.closed(start, end);
    }

    public int compareTo(MyIntRange that) {
        int res = -1;
        if (this.rng.lowerEndpoint() > that.rng.lowerEndpoint()) {
            res = 1;
        }
        return res;
    }

    public String toString() {
        return "[" + rng.lowerEndpoint() + ", " + rng.upperEndpoint() + "]";
    }
}

ありがとう

4

2 に答える 2

7

これは基本的にRangeSet、リリースされたばかりの Guava 14.0 で行うこととまったく同じですが、どの範囲をマージできるかを伝えるのではなく、マージを行います。

于 2013-03-01T02:33:29.660 に答える
3

基本的なアルゴリズム：

  1. 開始インデックスで間隔を並べ替える
  2. リストをウォークスルーします。ith項目 の場合：
    1. の終了インデックスをstアイテムiの開始インデックスと比較します。(i+1)
    2. 終了インデックスが大きい場合は、の終了インデックスをの終了インデックスに設定しi、要素i+1を削除しi+1ます。（これはそれらをマージします。）

時間計算量：O(nlgn)、最初のソートのため。（つまり、削除が正しく行われた場合。）

于 2013-03-01T02:17:06.637 に答える