8

間隔のリストが 2 つあります。list2 に既に存在する list1 からすべての時間を削除したいと思います。例: リスト 1:

[(0,10),(15,20)]

リスト 2:

[(2,3),(5,6)]

出力：

[(0,2),(3,5),(6,10),(15,20)]

ヒントはありますか？

一度に1つの間隔を削除しようとしましたが、別のアプローチを取る必要があるようです:

public List<Interval> removeOneTime(Interval interval, Interval remove){
    List<Interval> removed = new LinkedList<Interval>();
    Interval overlap = interval.getOverlap(remove);
    if(overlap.getLength() > 0){
        List<Interval> rms = interval.remove(overlap);
        removed.addAll(rms);
    }
    return removed;
}
4

2 に答える 2

7

この問題には、スイープ ライン アルゴリズムを使用してアプローチします。間隔の開始点と終了点はイベントであり、優先キューに入れられます。左から右に移動し、すべてのイベントで停止し、そのイベントに従って現在のステータスを更新するだけです。

Interval簡単にするために、次のクラスを使用する小さな実装を作成しました。

public class Interval {
    public int start, end;

    public Interval(int start, int end) {       
        this.start = start;
        this.end = end;
    }

    public String toString() {
        return "(" + start + "," + end + ")";
    }
}

前述のイベント ポイントは、次のクラスで表されます。

public class AnnotatedPoint implements Comparable<AnnotatedPoint> {
    public int value;
    public PointType type;

    public AnnotatedPoint(int value, PointType type) {
        this.value = value;
        this.type = type;
    }

    @Override
    public int compareTo(AnnotatedPoint other) {
        if (other.value == this.value) {
            return this.type.ordinal() < other.type.ordinal() ? -1 : 1;
        } else {
            return this.value < other.value ? -1 : 1;
        }
    }

    // the order is important here: if multiple events happen at the same point,
    // this is the order in which you want to deal with them
    public enum PointType {
        End, GapEnd, GapStart, Start
    }
}

さて、残っているのは、以下のコードに示すように、キューを構築してスイープを行うことです

public class Test {

    public static void main(String[] args) {        
        List<Interval> interval = Arrays.asList(new Interval(0, 10), new Interval(15, 20));
        List<Interval> remove = Arrays.asList(new Interval(2, 3), new Interval(5, 6));

        List<AnnotatedPoint> queue = initQueue(interval, remove);       
        List<Interval> result = doSweep(queue);

        // print result
        for (Interval i : result) {
            System.out.println(i);
        }
    }

    private static List<AnnotatedPoint> initQueue(List<Interval> interval, List<Interval> remove) {
        // annotate all points and put them in a list
        List<AnnotatedPoint> queue = new ArrayList<>();
        for (Interval i : interval) {
            queue.add(new AnnotatedPoint(i.start, PointType.Start));
            queue.add(new AnnotatedPoint(i.end, PointType.End));
        }
        for (Interval i : remove) {
            queue.add(new AnnotatedPoint(i.start, PointType.GapStart));
            queue.add(new AnnotatedPoint(i.end, PointType.GapEnd));
        }

        // sort the queue
        Collections.sort(queue);

        return queue;
    }

    private static List<Interval> doSweep(List<AnnotatedPoint> queue) {
        List<Interval> result = new ArrayList<>();

        // iterate over the queue       
        boolean isInterval = false; // isInterval: #Start seen > #End seen
        boolean isGap = false;      // isGap:      #GapStart seen > #GapEnd seen
        int intervalStart = 0;  
        for (AnnotatedPoint point : queue) {
            switch (point.type) {
            case Start:
                if (!isGap) {                   
                    intervalStart = point.value;
                }
                isInterval = true;
                break;
            case End:
                if (!isGap) {                   
                    result.add(new Interval(intervalStart, point.value));
                }
                isInterval = false;
                break;
            case GapStart:
                if (isInterval) {                   
                    result.add(new Interval(intervalStart, point.value));
                }               
                isGap = true;
                break;
            case GapEnd:
                if (isInterval) {
                    intervalStart = point.value;
                }
                isGap = false;
                break;
            }
        }

        return result;
    }
}

これにより、次の結果が得られます。

(0,2)
(3,5)
(6,10)
(15,20)
于 2013-04-30T17:05:45.020 に答える
1

インターバル ツリーを使用することをお勧めします。これにより、インターバルがツリー内のいずれかのインターバルと重複しているかどうかがすぐにわかります。

重複する間隔のセットを取得したら、タスクはかなり簡単になるはずです (interval1 は list1 から、interval2 は list2 / 間隔ツリーからの重複する間隔です): interval1 に interval2 が含まれている場合、2 つの新しい間隔 (interval1min、interval2min) が作成されます。 (interval2max、interval1max); interval1 に interval2 が含まれていない場合、新しい間隔 (interval1min, interval2min) または (interval2max, interval1max) が 1 つだけになります。

于 2013-04-30T16:07:16.587 に答える