2017-12-21 14 views
1

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

:(から)開始と終了(に)タイムスタンプによって区切ら

Periods

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にとって貴重です;)

+0

平均または "最速" 最悪の場合には、 "最速" がより重要ですか? – chux

+1

最も早い最悪の場合! – Simmoniz

+0

期間CとHは重複していますか? (A、B、A、C)、[A、B]、[A、B]、[A、B] E]、[A、H]、[A、...]はそれが目標であることを暗示するようではないが、数学的にはそうである。 – chux

答えて

2

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

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

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

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

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

+0

私はこのアプローチが好きです。私はそれを実装しようとし、ここに結果を投稿します。ありがとうございました ! – Simmoniz

0

の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']] 
関連する問題