Как правильно объединить перекрывающиеся диапазоны дат-времени в Python

Question

Я пытаюсь объединить перекрывающиеся диапазоны дат-времени. У меня есть список диапазонов даты и времени, как кортежи в списке:

data = [(datetime.datetime(2016, 1, 10, 13, 0), datetime.datetime(2016, 1, 10, 16, 0)), (datetime.datetime(2016, 1, 10, 14, 0), datetime.datetime(2016, 1, 10, 14, 0)), (datetime.datetime(2016, 1, 10, 22, 0), datetime.datetime(2016, 1, 10, 22, 0)), (datetime.datetime(2016, 1, 10, 23, 0), datetime.datetime(2016, 1, 11, 0, 30)), (datetime.datetime(2016, 1, 11, 2, 30), datetime.datetime(2016, 1, 11, 3, 30)), (datetime.datetime(2016, 1, 11, 13, 0), datetime.datetime(2016, 1, 11, 16, 0)), (datetime.datetime(2016, 1, 11, 14, 0), datetime.datetime(2016, 1, 11, 14, 0)), (datetime.datetime(2016, 1, 11, 20, 30), datetime.datetime(2016, 1, 11, 21, 30)), (datetime.datetime(2016, 1, 11, 22, 0), datetime.datetime(2016, 1, 11, 22, 0)), (datetime.datetime(2016, 1, 12, 2, 30), datetime.datetime(2016, 1, 12, 3, 30)), (datetime.datetime(2016, 1, 12, 13, 0), datetime.datetime(2016, 1, 12, 16, 0)), (datetime.datetime(2016, 1, 12, 14, 0), datetime.datetime(2016, 1, 12, 14, 0)), (datetime.datetime(2016, 1, 12, 19, 30), datetime.datetime(2016, 1, 12, 20, 30)), (datetime.datetime(2016, 1, 12, 22, 0), datetime.datetime(2016, 1, 12, 22, 0)), (datetime.datetime(2016, 1, 13, 2, 30), datetime.datetime(2016, 1, 13, 3, 30)), (datetime.datetime(2016, 1, 13, 13, 0), datetime.datetime(2016, 1, 13, 16, 0)), (datetime.datetime(2016, 1, 13, 14, 0), datetime.datetime(2016, 1, 13, 14, 0)), (datetime.datetime(2016, 1, 13, 20, 0), datetime.datetime(2016, 1, 13, 21, 0)), (datetime.datetime(2016, 1, 13, 21, 30), datetime.datetime(2016, 1, 13, 22, 0)), (datetime.datetime(2016, 1, 13, 22, 0), datetime.datetime(2016, 1, 13, 22, 0)), (datetime.datetime(2016, 1, 14, 2, 30), datetime.datetime(2016, 1, 14, 3, 30)), (datetime.datetime(2016, 1, 14, 13, 0), datetime.datetime(2016, 1, 14, 16, 0)), (datetime.datetime(2016, 1, 14, 14, 0), datetime.datetime(2016, 1, 14, 14, 0)), (datetime.datetime(2016, 1, 14, 22, 0), datetime.datetime(2016, 1, 14, 22, 0)), (datetime.datetime(2016, 1, 14, 22, 0), datetime.datetime(2016, 1, 14, 23, 0)), (datetime.datetime(2016, 1, 15, 2, 30), datetime.datetime(2016, 1, 15, 3, 30)), (datetime.datetime(2016, 1, 15, 13, 0), datetime.datetime(2016, 1, 15, 16, 0)), (datetime.datetime(2016, 1, 15, 14, 0), datetime.datetime(2016, 1, 15, 14, 0)), (datetime.datetime(2016, 1, 15, 20, 30), datetime.datetime(2016, 1, 15, 22, 0)), (datetime.datetime(2016, 1, 15, 22, 0), datetime.datetime(2016, 1, 15, 22, 0)), (datetime.datetime(2016, 1, 16, 2, 30), datetime.datetime(2016, 1, 16, 3, 30)), (datetime.datetime(2016, 1, 16, 13, 0), datetime.datetime(2016, 1, 16, 16, 0)), (datetime.datetime(2016, 1, 17, 2, 30), datetime.datetime(2016, 1, 17, 3, 30))] 

Вот мой текущий код:

import datetime 

def merge_date_ranges(data): 

    result = [] 

    for t1, t2 in ((data[i], data[i+1]) for i in range(len(data)-1)): 
     if t1[1] >= t2[0]: 
      result.append((min(t1[0], t2[0]), max(t1[1], t2[1]))) 
     else: 
      result.append(t1) 

Если T1 (первый диапазон даты и времени) и T2 (второй диапазон даты и времени) не перекрываются, то я просто добавьте T1 в новый список (результат). Если T1 и T2 DO перекрываются, я добавляю объединенный кортеж в новый список (результат).

Моя проблема в том, что происходит после слияния. Например:

T1 = (datetime.datetime(2016, 1, 10, 13, 0), datetime.datetime(2016, 1, 10, 16, 0)) 
T2 = (datetime.datetime(2016, 1, 10, 14, 0), datetime.datetime(2016, 1, 10, 14, 0)) 

T1 и T2 слиты и добавляется следующее в мой новый список:

(datetime.datetime(2016, 1, 10, 13, 0), datetime.datetime(2016, 1, 10, 16, 0)) 

Так что теперь я хочу, чтобы мой код (в следующей итерации для цикла) для сравнения объединенный кортеж (новый T1) со следующим диапазоном даты и времени в моем списке:

T1 = (datetime.datetime(2016, 1, 10, 13, 0), datetime.datetime(2016, 1, 10, 16, 0)) 
T2 = (datetime.datetime(2016, 1, 10, 22, 0), datetime.datetime(2016, 1, 10, 22, 0)) 

Но вместо этого, вот что T1 и T2 выглядеть следующим образом:

T1 = (datetime.datetime(2016, 1, 10, 14, 0), datetime.datetime(2016, 1, 10, 14, 0)) 
T2 = (datetime.datetime(2016, 1, 10, 22, 0), datetime.datetime(2016, 1, 10, 22, 0)) 

И T1 добавляется в мой новый список (чего я не хочу), потому что он уже был объединен ранее.

Но я просто не могу понять, как это сделать. Было бы проще, если бы я смог обновить свой первоначальный список, заменив T2 на объединенный кортеж и удалив T1. Но, как я понимаю, это невозможно или даже хорошая практика.

После недели вытягивания волос, я отправляю свой первый вопрос здесь в надежде, что кто-то может помочь мне вернуть мое здравомыслие. :)

Обновление В принципе, я хочу, чтобы в итоге появился новый список, где диапазоны дат-времени не совпадают.

Answer 1

Я думаю, это то, что вы хотите. Дайте ему испытание и комментарий:

def merge_date_ranges(data): 
    result = [] 
    t_old = data[0] 
    for t in data[1:]: 
     if t_old[1] >= t[0]: #I assume that the data is sorted already 
      t_old = ((min(t_old[0], t[0]), max(t_old[1], t[1]))) 
     else: 
      result.append(t_old) 
      t_old = t 
    else: 
     result.append(t_old) 
    return result 

Я предполагаю, что сроки уже отсортированы.

BTW, я вижу, что единственные странные даты - это те, которые являются одиночными днями, возможно, вы должны исправить свои входные данные.

salida = merge_date_ranges(data) 
for item in [t for t in data if t not in salida]: 
    print item 

(datetime.datetime(2016, 1, 10, 14, 0), datetime.datetime(2016, 1, 10, 14, 0)) 
(datetime.datetime(2016, 1, 11, 14, 0), datetime.datetime(2016, 1, 11, 14, 0)) 
(datetime.datetime(2016, 1, 12, 14, 0), datetime.datetime(2016, 1, 12, 14, 0)) 
(datetime.datetime(2016, 1, 13, 14, 0), datetime.datetime(2016, 1, 13, 14, 0)) 
(datetime.datetime(2016, 1, 13, 22, 0), datetime.datetime(2016, 1, 13, 22, 0)) 
(datetime.datetime(2016, 1, 14, 14, 0), datetime.datetime(2016, 1, 14, 14, 0)) 
(datetime.datetime(2016, 1, 14, 22, 0), datetime.datetime(2016, 1, 14, 22, 0)) 
(datetime.datetime(2016, 1, 15, 14, 0), datetime.datetime(2016, 1, 15, 14, 0)) 
(datetime.datetime(2016, 1, 15, 22, 0), datetime.datetime(2016, 1, 15, 22, 0)) 

Answer 2

Редактировать: с учетом новой информации вы все равно должны делать цикл, но основывать его на логическом значении и проверять наложения.

import datetime 

def merge_date_ranges(data): 

    input = data 
    result = [] 
    overlap = True # we assume there's overlap to begin with 

    while(overlap): 
     overlap = False # will remain false unless overlap is found 

     for t1, t2 in ((input[i], input[i+1]) for i in range(len(input)-1)): 
      if t1[1] >= t2[0]: 
       overlap = True # an overlap was found, so loop will continue 
       result.append((min(t1[0], t2[0]), max(t1[1], t2[1]))) 
      else: 
       result.append(t1) 

     if(overlap): 
      input = result # preparing the next round 

    return result