Оптимизируйте код до 0 (N) для проблемы времени встречи

Question

Учитывая список времени начала и окончания встреч людей, найдите количество людей в данное время. Время будет дано в виде целых чисел. Например:

Ввод

[ [ 12, 14] ,[12,15],[14,16],[13,15]] 

Выход должен вернуть

[ 0,0,0,0,0,0,0,0,0,0,0,2,3,4,3,1]

Как делать по линейному времени?

Я могу сделать это за O(n^2).

Answer 1

Предполагается, что вы смотрите только один день, а N - это количество временных пар (которые не более 24 часов на собрании):

output = [0 for i in range(24)] # O(1)

for [start, end] in meetings: # N iterations
    for o in range(end - start + 1): # At most 24 iterations per outer iteration
        output[o + start - 1] += 1

Самое большее, внутренний цикл будетвыполняется 24 раза для каждой пары, постоянный наихудший случай, и внешний цикл будет выполнен N раз.Таким образом, у нас наихудший случай O(24N), который равен O(N).