セッションの重複を見つける

Question

私は開始タイムスタンプと終了タイムスタンプを持つ任意の数のセッションを持っています

これらのセッションの一部は重複しています。複数のセッションが同時に重複する可能性があります。

重複の秒数を検出できるアルゴリズムを見つけようとしています。 IEのような3つのセッションが与えられました

-ID-|-start-|-end-| 
--1-|-----4-|--10-| 
--2-|-----5-|--12-| 
--3-|-----8-|--13-| 

セッションが重複する秒数を返します。

私はinterval treesについて読んで、this oneのようなpythonパッケージを見てきました。

ただし、特定のレコードセットのオーバーラップの秒数を取得する方法がわかりません。あなたはアルゴリズムやパッケージを知っていますか？ Pythonが優先されていますが、他の言語に開放されており、私は再実装することができます。

Answer 1

ソートのためにO（n log n）の複雑さを伴う私の心に来た最初のアイデア。 startsとendsがすでにソートされている場合、アルゴリズムはO（n）の複雑さを持ちます。

int findOverlappingTimes(int[] starts, int ends[]) { 

    // TODO: Sort starts array 
    // TODO: Sort ends array 
    // TODO: Assert starts.length == ends.length 

    int currStartsIndex = 0; 
    int currEndsIndex = 0; 

    int currOverlaps = 0; 
    int lastOverlapIndex = -1; 

    int result = 0; 

    while (currEndsIndex < ends.length) { 

     if (currStartsIndex < starts.length && starts[currStartsIndex] < ends[currEndsIndex]) { 
      if (++currOverlaps == 2) { // Start counting if at least two intervals overlap 
       lastOverlapIndex = currStartsIndex; 
      } 
      currStartsIndex++; 
     } else { 
      if (--currOverlaps <= 1 && lastOverlapIndex != -1) { // Stop counting 
       result += ends[currEndsIndex] - starts[lastOverlapIndex]; 
       lastOverlapIndex = -1; 
      } 
      currEndsIndex++; 
     } 

    } 

    return result; 
} 

ご入力に対する出力は

findOverlappingTimes(new int[] { 4, 5, 8 }, new int[] { 10, 12, 13 }) 

戻り7を設定します。

アルゴリズムの背後にある基本的な考え方は、セッションを繰り返し、現在重なっているセッションの数を数えることです。現時点で少なくとも2つのセッションが重複している場合は重複時間のカウントを開始し、重複が終了した場合は重複時間のカウントを停止します。ここで

いくつかのより多くのテストケースとそれぞれ出力されています

findOverlappingTimes(new int[] { 0 }, new int[] { 0 }) = 0 
findOverlappingTimes(new int[] { 10 }, new int[] { 10 }) = 0 
findOverlappingTimes(new int[] { 10 }, new int[] { 20 }) = 0 
findOverlappingTimes(new int[] { 10, 10 }, new int[] { 10, 10 }) = 0 
findOverlappingTimes(new int[] { 10, 10 }, new int[] { 11, 11 }) = 1 
findOverlappingTimes(new int[] { 10, 10, 10 }, new int[] { 11, 11, 12 }) = 1 
findOverlappingTimes(new int[] { 10, 10, 10, 50, 90, 110 }, new int[] { 11, 12, 12, 100, 150, 160 }) = 52 
findOverlappingTimes(new int[] { 4, 5, 8, 100, 200, 200, 300, 300 }, new int[] { 10, 12, 13, 110, 200, 200, 320, 330 }) = 27