Python: Алгоритм

Question

Вопрос: Учитывая список неупорядоченных временных меток, найдите самый большой промежуток времени, который перекрывается
Например: [1,3], [10,15], [2,7], [11,13 ], [12,16], [5,8] => [1,8] и [10,16]

Мне было предложено решить вышеуказанный вопрос.

Мой первоначальный подход был следующим:

times = [[1,3],[10,15],[2,7],[11,13],[12,16],[5,8]] 
import itertools 
def flatten(listOfLists): 
    return itertools.chain.from_iterable(listOfLists) 
start = [i[0] for i in times] 
end = [i[1] for i in times] 
times = sorted(list(flatten(times))) 
# 1=s, 2=s, 3=e, 5=s, 7=e, 8=e, 10=s, 11=s, 12=s, 13=e, 15=e, 16=e 
num_of_e = 0 
num_of_s = 0 
first_s = 0 
for time in times: 
    if first_s == 0: 
     first_s = time 
    if time not in end: 
     num_of_s += 1 
    if time in end: 
     num_of_e += 1 
     if num_of_e == num_of_s: 
      num_of_e = 0 
      num_of_s = 0 
      print [first_s, time] 
      first_s = 0 

Тогда спрашивающий настаивал, что я должен решить, заказав раз первым, потому что «это лучше», так что я сделал следующее

times = [[1,3],[10,15],[2,7],[11,13],[12,16],[5,8]] 
def merge(a,b): 
    return[min(a[0],b[0]), max(a[1],b[1])] 
times.sort() 
# [1,3] [2,7] [5,8] [10,15] [11,13] [12,16] 
cur = [] 
for time in times: 
    if not cur: 
     cur = time 
     continue 
    if time[0] > cur[0] and time[0] < cur[1]: 
     cur = merge(time,cur) 
    else: 
     print cur 
     cur = time 
print cur 

Есть ли такая вещь, как «лучший» подход (или, может быть, другой подход, который может быть лучше)? Я знаю, что смогу его разглядеть и посмотреть, какой из них быстрее или просто оценивать на основе большой записи O (как O (N) для фактической рабочей части).

Просто хотелось посмотреть, есть ли у вас какие-либо мнения по этому поводу?
Какой из них вы бы предпочли и почему?
Или, может быть, другие способы сделать это?

Answer 1

Вот предложение для ускользаете риски, связанные с time in end время вычислений и конкретные случаями вопросов:

times = [[1,3],[10,15],[2,7],[11,13],[12,16],[5,8]] 
start = [(i[0], 0) for i in times] 
end = [(i[1], 1) for i in times] 
# Using 0 for start and 1 for end ensures that starts are resolved before ends 
times = sorted(start + end) 
span_count = 0 
first_s = 0 
for time, is_start in times: 
    if first_s == 0: 
     first_s = time 
    if is_start == 0: 
     span_count += 1 
    else: 
     span_count -= 1 
     if span_count == 0: 
      print [first_s, time] 
      first_s = 0 

Кроме того, он имеет легко вычислимую сложность O(n) (actual work) + O(n*log(n)) (sort) = O(n*log(n))

Answer 2

Скорость часто является наиболее важным фактором при оценке алгоритма, но она может быть не единственной. Но давайте сначала посмотрим на скорость.

В этом случае есть два вида скорости: асимптотический (что является большим Ω - Θ -O обозначение характеризуется) и неасимптотическое. Даже если два алгоритма имеют одно и то же асимптотическое поведение, все же можно выполнить значительно лучше, чем другие, из-за других затрат в алгоритме, которые будут значительными при меньших размерах данных.

В вашем первом алгоритме вы перебираете список два раза перед его сортировкой, а затем перебираете список в третий раз после его сортировки. Во втором ответе вы повторяете только один раз. Я бы ожидал, что второй будет быстрее, но в Python производительность иногда может быть удивительной, поэтому неплохо измерить, нужна ли вам скорость.

Вы также можете оценить использование памяти алгоритмом. Ваш первый алгоритм создает два временных списка времени начала и окончания, а третий временный список содержит отсортированные промежутки времени. Это может быть дорого, если набор данных большой! Второй алгоритм позволяет избежать этого, но создает новый список длины 2 каждый раз, когда вызывается merge. Это все равно может быть выделено значительное количество памяти, и может быть что-то еще более оптимистичное. Также может быть некоторое использование памяти, скрытое за кулисами: например, использование sort не может использовать гораздо меньше памяти, чем sorted, когда вы смотрите на то, как оно реализовано.

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