6

次の問題を解決しようとしています: N 時間間隔が与えられ、それぞれが (開始、終了) として指定され、重複せず、開始に基づいて並べ替えられている - 特定の日付を含む間隔を見つけます。たとえば、次のようになります。

[1,4] [5,8] [9,10][11,20]

3 は最初のインターバルに、15 は 4 番目のインターバルに分類されます。

これまでのところ、次の基本的なアイデアがありました。

  1. バイナリ検索を使用して、対応する間隔 (Log N) を見つけることができます。
  2. いくつかの間隔だけが大きく、残りは小さい場合があるため、期間に基づいて間隔を並べ替える価値があるかもしれません。次に、統計的に、ほとんどの場合、最長の間隔 (O(1)) に「ヒット」しますが、これが N の最悪のケースの複雑さになる場合があります。

2つのアプローチを組み合わせる余地があるかどうかを考えていました。もう 1 つのアイデアは、期間に基づいて並べ替え、すべての間隔をツリーに挿入し、開始日で比較することです。これは、最悪の場合、最長の期間が時系列順に並んでいる場合、このアプローチのパフォーマンスは 2 に等しくなります。

私が想像した理想的な解決策は、一番上の最長の間隔を含むツリー (または同様のデータ構造) を持つことであり、2 つの分岐には次の 2 つの最長の間隔などがあります。ただし、分岐する方法がわかりませんつまり、長さに基づいて挿入するという明示的な仮定を行うため、ツリーの左側または右側を実際に破棄することはできません。

どんなコメントでも大歓迎です。

4

6 に答える 6

0

JodaTimeと TimeSlotsを使用して同様のものを実装しました (これは Joda Period とほぼ同等です)。Period は、DateTime 型の開始と終了を持つカスタム クラスでした。終了日でソートされた期間の TreeSet を保持しました。

タイムスロット クラス:

public class TimeSlot<T> {
    private DateTime start;
    private DateTime end;

    // accessors
    ...
}

ユーティリティ メソッド:

public TimeSlot<T> getTimeSlot(DateTime pointInTime) {
    for (TimeSlot<T> ts : getCounterTimeSlotSet()) {
        if (ts.getPeriod().isDateInRange(pointInTime)) {
            return ts;
        }
    }
    return null;
}


public boolean isDateInRange(DateTime date) {
    if (date == null) {
        return false;
    }

    return date.isAfter(this.start.minusMillis(1)) 
        && date.isBefore(this.end.plusMillis(1));
}

最近、アレンの間隔代数を実装するライブラリを見つけました。役に立つかもしれません。

于 2012-12-24T10:13:03.377 に答える