重複する期間（または時間の範囲）を検出する最速の方法

Question

私はタイムスタンプの開始と終了によって識別される多くの期間があると仮定します。どの期間で重複しているかを検出する最も簡単な方法は何ですか？ここでは一例

：（から）開始と終了（に）タイムスタンプによって区切ら

9異なる期間、。

A = [ from : 7s , to : 11s] 
B = [ from : 1s, to : 8s] 
C = [ from : 9s, to : 12s] 
D = [ from : 4s, to : 7s] 
E = [ from 10s, to: 15s] 
F = [ from 0s, to : 5s] 
G (oops i skipped it when drawing the image!) 
H = [ from: 5s, to: 9s] 
I = [ from: 11s, to: 13s] 
J = [ from: 7s, to: 14s] 

次の結果を得るには、すべての重複期間をできるだけ早く取得する方法を教えてください。 B、D]、[B、F]、[B、F]、[A、B]、[A、E]、[A、H]、[A、J] D、H]、[D、J]、[E、I]、[C、 、[E、J]、[H、J]、実際のタイムスタンプとの[I、J]

JSFiddle of my own solution here

および他の同様jsfiddle今回は、1月から18に午前8時との間に2017 3月午後のEDTには、多くのものがあります。

JSFiddle with lots of timestamps

誰かが続行する迅速な方法を見つけることができれば、それは素晴らしいことです！各ミリ秒は、私がheheにとって貴重です;）

Answer 1

すべての時間を、それが属するセグメントと開始/終了ビットでそれぞれマーキングします。

次に、どのセグメントにいるかを示すリストを保持します（最初は空です）。

時間のリストを繰り返します。時間がセグメントXに属する場合、開始時間であれば、Xを第2のリストに加える。終了時刻であれば、2番目のリストからXを削除します。 2つ目のリストは、常にどのセグメントが重なっているかを示します。

big-Oを気にするセグメントが十分ある場合、最初のソートはO（N Log N）です。 反復はO（N）です。

もちろん、big-Oにはカウントしないでください。それでもなお一定の要因があります。 Here's how I do it.

Answer 2

のPython：

from pprint import pprint as pp 

intervals = [ 
    (7 , 11, 'A'), 
    (1, 8, 'B'), 
    (9, 12, 'C'), 
    (4, 7, 'D'), 
    (10, 15, 'E'), 
    (0, 5, 'F'), 
    (5, 9, 'H'), 
    (11, 13, 'I'), 
    (7, 14, 'J'), 
] 
intervals.sort() # sort on interval start, then end if starts are equal 
ans = [] 
for n0, (_, end0, name0) in enumerate(intervals[:-1]): 
    for n1, (start1, _, name1) in enumerate(intervals[n0 + 1:]): 
     if start1 < end0: 
      ans.append(sorted((name0, name1))) 
     else: 
      break 
pp(sorted(ans)) 

出力：

[['A', 'B'], 
['A', 'C'], 
['A', 'E'], 
['A', 'H'], 
['A', 'J'], 
['B', 'D'], 
['B', 'F'], 
['B', 'H'], 
['B', 'J'], 
['C', 'E'], 
['C', 'I'], 
['C', 'J'], 
['D', 'F'], 
['D', 'H'], 
['E', 'I'], 
['E', 'J'], 
['H', 'J'], 
['I', 'J']]