1

検索の開始日と終了日のみと重複するすべての間隔をリストから取得するために、開始日と終了日を指定して間隔のリストをクエリする代わりに、次の方法が最適です。

From a list of date intervals, 
Find all unique sets of intervals
Where every interval in each set overlaps with each other interval in that set

整数の例を使用して、整数間隔のリストを取得します[{1,3},{2,4},{4,5},{5,7},{6,8}]。このリストから、各セットのすべての間隔が互いに重複しているすべての一意の間隔セットを次に示します。

{ {1,3}, {2,4} }
{ {2,4}, {4,5} }
{ {4,5}, {5,7} }
{ {5,7}, {6,8} }

DateInterval のクラスは次のとおりです。

from datetime import datetime
class DateInterval(object):
    def __init__(self, start_time, end_time):
        self.start_time = datetime.strptime(start_time, '%Y-%m-%d %H:%M:%S')
        seld.end_time = datetime.strptime(end_time, '%Y-%m-%d %H:%M:%S')

    ''' eq, gt, hash methods removed for clarity '''

次のように、start_time の昇順で並べ替えられた間隔のリストを受け取ります。

intervals = [DateInterval(start_time='2015-01-01 08:00:00', end_time='2015-01-01 08:30:00'),
             DateInterval(start_time='2015-01-01 08:00:00', end_time='2015-01-01 10:00:00'),
             DateInterval(start_time='2015-01-01 09:00:00', end_time='2015-01-01 11:00:00'),
             DateInterval(start_time='2015-01-01 10:00:00', end_time='2015-01-01 12:00:00'),
             DateInterval(start_time='2015-01-01 13:00:00', end_time='2015-01-01 16:00:00'),
             DateInterval(start_time='2015-01-01 14:00:00', end_time='2015-01-01 17:00:00'),
             DateInterval(start_time='2015-01-01 15:00:00', end_time='2015-01-01 18:00:00'),
             DateInterval(start_time='2015-01-01 20:00:00', end_time='2015-01-01 22:00:00'),
             DateInterval(start_time='2015-01-01 20:00:00', end_time='2015-01-01 22:00:00')
             ]

(この例のリストでは、開始日と終了日は常に均等に 1 時間に収まります。ただし、代わりに任意の秒 (またはミリ秒) に収まる可能性があります)。重複する間隔に関するstackoverflowの質問の完全なリストを検索した後、間隔ツリーは日付間隔には不適切であることがわかりました)。

私の軽く最適化された総当り法は、3 つのタスクで構成されています

  1. 各セット内の少なくとも 1 つの間隔がそのセット内の他のすべての間隔と重複する、一意でない間隔のセットをすべて識別します
  2. 手順 1 の結果の重複を排除して、各セットの少なくとも 1 つの間隔がそのセットの他のすべての間隔と重複している一意の間隔セットをすべて見つけます。
  3. 1 の結果から、1 つのセットの各間隔がそのセットの他のすべての間隔と重複するセットのみを見つけます。

1.

以下は、間隔リスト内の各間隔を他のすべての間隔と単純に比較することにより、各セット内の 1 つの間隔のみがそのセット内の他のすべての間隔と重複するすべての非一意のセットを検索します。間隔のリストが日時の昇順でソートされていることを前提としています。これにより、break最適化が可能になります。

def search(intervals, start_date, end_date):
    results = []
    for interval in intervals:
        if end_date >= interval.start_time:
            if start_date <= interval.end_time:
                results.append(interval)
        else:
            break # This assumes intervals are sorted by date time ascending

searchは次のように使用されます。

brute_overlaps = []
for interval in intervals:
    brute_overlaps.append(search(intervals, interval.start_time, interval.end_time))

2.

以下は、セットのリストを重複排除します。

def uniq(l):
    last = object()
    for item in l:
        if item == last:
            continue
        yield item
        last = item

def sort_and_deduplicate(l):
    return list(uniq(sorted(l, reverse=True)))

3.

そして、以下は、セット内の各間隔をそのセット内の他のすべての間隔と単純に比較することによって、各セット内の各間隔がそのセット内の他のすべての間隔と重複するすべてのセットを見つけます。

def all_overlap(overlaps):
    results = []
    for overlap in overlaps:
        is_overlap = True
        for interval in overlap:
            for other_interval in [o for o in overlap if o != interval]:
                if not (interval.end_time >= other_interval.start_time and interval.start_time <= other_interval.end_time):
                    is_overlap = False
                    break # If one interval fails
             else:        # break out of
                 continue # both inner for loops
             break        # and try next overlap

        if is_overlap: # all intervals in this overlap set overlap with each other
            results.append(overlap)
    return results
4

1 に答える 1

0

各間隔がセット内の他のすべての間隔とオーバーラップする必要がある一連の間隔には、それらがすべてオーバーラップする共通点があります。逆に、ある時点ですべての間隔を照会すると、相互に重複する一連の間隔が得られます。

それを念頭に置いて、あなたの問題は「クエリしているポイントを変更することによって、取得できる間隔の個別のサブセットは何ですか?」に減少します。これらの異なるサブセットをすべて取得する簡単な方法は、重複する間隔が変化する必要があるイベントの場所を見つけ、イベントの各ペア間のポイントでクエリを実行することです。

間隔の場合、イベントは任意の間隔開始または任意の間隔終了に対応します。したがって、開始して終了していない間隔のセットを追跡しながら、開始および停止する間隔を左から右にスキャンするだけです。これにより、相互に重複する最大のサブセットがすべて得られます。

疑似コードで...

maximalMutuallyOverlappingSubsets =
    intervals
    .flatMap(e => [(e.start, e, true),
                   (e.end, e, false)])
    .sortedBy(e => e[0]).
    .scan({}, (prevSet, (x, interval, add)) =>
        if add
        then prevSet + {interval}
        else prevSet - {interval})
    .distinct() - {{}}

O(n lg n)ソートが最もコストのかかるステップであり、時間内に実行されます。

慣れていない方のために説明すると、flatMapはリストの各アイテムを結果のコレクションに射影し、結果のコレクションのすべてのアイテムを連結します。スキャンは指定されたアキュムレータから開始し、中間結果を生成しながら、指定された関数を使用して次の項目をアキュムレータに結合し続けます。

于 2015-03-11T22:11:40.693 に答える