合併具有重疊時間範圍的時間範圍元組列表

Question

我有一個元組列表，其中每個元組都是(start-time, end-time)。我正在嘗試合併所有重疊的時間範圍並返回不同時間範圍的列表。 例如

[(1, 5), (2, 4), (3, 6)] ---> [(1,6)] 
[(1, 3), (2, 4), (5, 8)] ---> [(1, 4), (5,8)] 

這是我如何實現它。

# Algorithm 
# initialranges: [(a,b), (c,d), (e,f), ...] 
# First we sort each tuple then whole list. 
# This will ensure that a<b, c<d, e<f ... and a < c < e ... 
# BUT the order of b, d, f ... is still random 
# Now we have only 3 possibilities 
#================================================ 
# b<c<d: a-------b   Ans: [(a,b),(c,d)] 
#     c---d 
# c<=b<d: a-------b   Ans: [(a,d)] 
#    c---d 
# c<d<b: a-------b   Ans: [(a,b)] 
#   c---d 
#================================================ 
def mergeoverlapping(initialranges): 
    i = sorted(set([tuple(sorted(x)) for x in initialranges])) 

    # initialize final ranges to [(a,b)] 
    f = [i[0]] 
    for c, d in i[1:]: 
     a, b = f[-1] 
     if c<=b<d: 
      f[-1] = a, d 
     elif b<c<d: 
      f.append((c,d)) 
     else: 
      # else case included for clarity. Since 
      # we already sorted the tuples and the list 
      # only remaining possibility is c<d<b 
      # in which case we can silently pass 
      pass 
    return f 

我想如果

1. 弄清楚的是一個在某些Python模塊的內置功能，可以更有效地做到這一點？或
2. 是否有一種更爲pythonic的方式來實現相同的目標？

您的幫助表示感謝。謝謝！然後

Answer 1

一些使其更有效的方法，Pythonic：

1. 消除t因爲該算法應該在主循環期間刪除重複。
2. 如果您只需要遍歷結果，請使用yield來生成值。
3. 減少中間對象的構建，例如：將tuple()調用移動到生成最終值的位置，使您不必構造並丟棄額外的元組，並重新使用列表saved來存儲當前時間範圍比較。

代碼：

def merge(times): 
    saved = list(times[0]) 
    for st, en in sorted([sorted(t) for t in times]): 
     if st <= saved[1]: 
      saved[1] = max(saved[1], en) 
     else: 
      yield tuple(saved) 
      saved[0] = st 
      saved[1] = en 
    yield tuple(saved) 

data = [ 
    [(1, 5), (2, 4), (3, 6)], 
    [(1, 3), (2, 4), (5, 8)] 
    ] 

for times in data: 
    print list(merge(times)) 

Answer 2

排序元組列表中，如果t1.right> = t2.left =>合併 ，並與新的列表重新啓動，...

- >

def f(l, sort = True): 
    if sort: 
     sl = sorted(tuple(sorted(i)) for i in l) 
    else: 
     sl = l 
    if len(sl) > 1: 
     if sl[0][1] >= sl[1][0]: 
      sl[0] = (sl[0][0], sl[1][1]) 
      del sl[1] 
      if len(sl) < len(l): 
       return f(sl, False) 
    return sl 

Answer 3

的分類部分：使用標準的排序，比較的元組已經以正確的方式。

sorted_tuples = sorted(initial_ranges) 

合併部分。它也消除了重複的範圍，所以不需要set。假設你有current_tuple和next_tuple。

c_start, c_end = current_tuple 
n_start, n_end = next_tuple 
if n_start <= c_end: 
    merged_tuple = min(c_start, n_start), max(c_end, n_end) 

我希望邏輯足夠清楚。

要查看下一個元組，可以使用索引訪問sorted tuples;無論如何，這是一個完全已知的序列。

Answer 4

對所有邊界進行排序，然後取所有對，其中邊界結束後是邊界開始。

def mergeOverlapping(initialranges): 
    def allBoundaries(): 
     for r in initialranges: 
      yield r[0], True 
      yield r[1], False 

    def getBoundaries(boundaries): 
     yield boundaries[0][0] 
     for i in range(1, len(boundaries) - 1): 
      if not boundaries[i][1] and boundaries[i + 1][1]: 
       yield boundaries[i][0] 
       yield boundaries[i + 1][0] 
     yield boundaries[-1][0] 

    return getBoundaries(sorted(allBoundaries())) 

嗯，這不是很美，但很有趣，至少寫！

編輯：多年後，upvote後，我意識到我的代碼是錯的！這是新版本只是爲了好玩：

def mergeOverlapping(initialRanges): 
    def allBoundaries(): 
     for r in initialRanges: 
      yield r[0], -1 
      yield r[1], 1 

    def getBoundaries(boundaries): 
     openrange = 0 
     for value, boundary in boundaries: 
      if not openrange: 
       yield value 
      openrange += boundary 
      if not openrange: 
       yield value 

    def outputAsRanges(b): 
     while b: 
      yield (b.next(), b.next()) 

    return outputAsRanges(getBoundaries(sorted(allBoundaries()))) 

基本上我標誌着邊界爲-1或1，然後在打開和關閉括號之間的平衡是由零值，只能輸出它們進行排序。

Answer 5

已經很晚了，但可能會幫助有人找這個。我有類似的問題，但與字典。給定一個時間範圍列表，我希望找到重疊並儘可能合併它們。稍加修改，以@samplebias的回答使我這個：

合併功能：

def merge_range(ranges: list, start_key: str, end_key: str): 
    ranges = sorted(ranges, key=lambda x: x[start_key]) 
    saved = dict(ranges[0]) 

    for range_set in sorted(ranges, key=lambda x: x[start_key]): 
     if range_set[start_key] <= saved[end_key]: 
      saved[end_key] = max(saved[end_key], range_set[end_key]) 
     else: 
      yield dict(saved) 
      saved[start_key] = range_set[start_key] 
      saved[end_key] = range_set[end_key] 
    yield dict(saved) 

數據：

data = [ 
    {'start_time': '09:00:00', 'end_time': '11:30:00'}, 
    {'start_time': '15:00:00', 'end_time': '15:30:00'}, 
    {'start_time': '11:00:00', 'end_time': '14:30:00'}, 
    {'start_time': '09:30:00', 'end_time': '14:00:00'} 
] 

執行：

print(list(merge_range(ranges=data, start_key='start_time', end_key='end_time'))) 

輸出：

[ 
    {'start_time': '09:00:00', 'end_time': '14:30:00'}, 
    {'start_time': '15:00:00', 'end_time': '15:30:00'} 
]