4

皆さん、

この問題はかなり前に聞いたことがあります。いくつかの構成要素または他の効率的な手段を使用するなど、これを行うことのいくつかのビューを取得するために、それを投稿することを考えました(特殊なツリーである可能性があります)

ペア (5,18) (12,23) (15,30) の一連の範囲が与えられた場合

それらを、セット内の他の範囲と重なって見えるすべての可能なサブ範囲に分割します。(5,11) (12,14) (15,18) (19,23) (24,30) のように

ありがとうございます...

ラージャン...

PS これは標準的な問題です。もしそうなら、その名前を教えてください

4

3 に答える 3

5

すべての範囲のエンドポイントをリストにまとめますが、それらを開始点/終了点としてマークします。

[(5, S), (18, E), (12, S), (23, E), (15, S), (30, E)]

それらを位置で並べ替え、始点を終点の前に置くことで関係を壊します。

[(5, S), (12, S), (15, S), (18, E), (23, E), (30, E)]

次に、このリストを反復処理して範囲を計算し、これまでに処理した開始点から終了点を引いた数を追跡します。開始点が表示された場合、それは出力する新しい範囲の開始です。カウントが正の場合、最初に現在の範囲を終了する必要があります。エンドポイントが表示されたら、現在の範囲を終了します。

于 2010-12-01T09:14:13.837 に答える
1

何かが足りないのかもしれませんが、これは単純な解決策のように思えます: C++ STL セット コンテナー内のすべての数値をスローします。自動的に昇順で並べ替えられます。したがって、次のように読み上げられます: 5,12,15,18,23,30 したがって、オーバーラップを許容できる場合: (5,12) (12,15) (15,18), (18,23) ( 23,30) は、最初と最後を除いてすべての数字を 2 回繰り返し、2 つの数字をグループ化することによって構築される範囲です。

オーバーラップが許容できない場合は、リストに数字を繰り返すのではなく、インクリメントした数字を入れて範囲を構築できます。

于 2013-07-11T01:39:11.380 に答える
1

わかりました、かなりいじくり回した後、明らかに機能するバージョンを実装することができました。したがって、実用的なソリューションを探している人のために、これが私のものです：

private static class RangeVal implements Comparable<RangeVal> {
    public final BigInteger value;
    public int count;

    public RangeVal(BigInteger value, int count) {
        super();
        this.value = value;
        this.count = count;
    }

    @Override
    public String toString() {
        return value + (isStart() ? "S" : "E") + count;
    }

    @Override
    public int compareTo(RangeVal o) {
        // Sort by value first
        int v = value.compareTo(o.value);
        if (v != 0)
            return v;
        // Then sort Starts before ends
        return -count;
    }

    public boolean isStart() {
        return count > 0;
    }

}

/**
 * Sort a List of ranges by their number, then start/end and merge multiple
 * start/ends
 * 
 * @param temp
 *            a list of RangeVal which can be unsorted
 */
private static void preSort(List<RangeVal> temp) {
    Collections.sort(temp);
    RangeVal last = null;
    for (Iterator<RangeVal> iterator = temp.iterator(); iterator.hasNext();) {
        RangeVal rangeVal = iterator.next();
        if ((last != null) && last.value.equals(rangeVal.value) && (last.isStart() == rangeVal.isStart())) {
            iterator.remove();
            last.count += rangeVal.count;
        } else
            last = rangeVal;
    }
}

/**
 * Splits a list into ValueRange Objects that do not overlap each other, but
 * fully represent the ranges given by value
 * 
 * @param value
 *            a list of RangeVal Objects that need to be split
 * @return
 */
private static SortedSet<ValueRange> split(List<RangeVal> value) {
    preSort(value);
    SortedSet<ValueRange> res = new TreeSet<ValueRange>();
    int count = 0;
    BigInteger start = null;
    for (RangeVal rangeVal : value) {
        count += rangeVal.count;
        if (rangeVal.isStart()) {
            if (start != null) {
                //If there was an unended start, then we have to end it just one before the new start
                res.add(new ValueRange(start, rangeVal.value.subtract(BigInteger.ONE)));
            }
            //Set the start to the current Element
            start = rangeVal.value;
        } else {
            //End the current range at this Element
            res.add(new ValueRange(start, rangeVal.value));
            if (count > 0) {
                //If we expect another end later, the element following this will have to start one after
                start = rangeVal.value.add(BigInteger.ONE);
            } else
                //No new range anymore
                start = null;
        }
    }
    return res;
}

public static void main(String[] args) {
    // 5->8 9->10 11
    System.out.println(split(createRanges(5, 8, 9, 10, 11, 11)));
    // 5, 6->7, 8, 9, 10
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9)));
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9)));
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9, 6, 11, 8, 9)));
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9, 6, 11, 8, 9, 14, 18)));
}

private static List<RangeVal> createRanges(int... r) {
    List<RangeVal> temp = new LinkedList<RangeVal>();
    for (int i = 0; i < r.length; i++) {
        temp.add(new RangeVal(BigInteger.valueOf(r[i]), (i % 2) == 0 ? 1 : -1));
    }
    System.out.println("HDLSimulator.createRanges()" + temp);
    return temp;
}
于 2012-06-19T11:35:43.007 に答える