Оптимизация данной задачи для линейного времени, не беспокоясь о пространстве

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*m).

Чтобы найти каждый из выходных данных, отсканируйте входные данные и найдите общее количество людей в данный момент времени. Это требует O(n*m) n = размер ввода, m = размер вывода

Answer 1

Хитрость для этого за время O (n + m):

1. Найдите требуемый размер выходного массива (время O (n))
2. Выделитеout массив и заполнить его нулями (O (м) время)
3. Для каждого [a,b] на входе, out[a]+=1; out[b+1]-=1 (O (N) время)
4. Заменить каждый элементна выходе с совокупной суммой всех элементов до этой точки.(O (м) время).Например for (int i=1; i<out.length; ++i) out[i]+=out[i-1];

Answer 2

Очевидный алгоритм работает довольно хорошо:

def schedule(spans):
  s = [0] * max(map(max, spans))
  for lo, hi in spans:
    for t in range(lo - 1, hi):
      s[t] += 1
  return s

print str(schedule([[12, 14],[12,15],[14,16],[13,15]]))

Это O (L + n), где L - общая длина всех промежутков, а n - размер выходных данных.

Тогда:

$ python foo.py
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 4, 3, 1]

Теперь, если у вас много перекрывающихся интервалов, то вы можете использовать алгоритм 1d линии развертки для вычисления результата за O (n log n + m) времени, где n - число интервалов, а m - количество выходных единиц времени.

Примерно так, хотя я не буду утверждать, что это совершенно правильно:

def schedule_faster(spans):
  events = []
  for lo, hi in spans:
    events.append((lo, '+'))
    events.append((hi + 1, '-'))
  events.sort()
  s = [0] * max(map(max, spans))
  n = 0
  t_last = events[0][0]
  for t, dir in events:
    if t != t_last:
      for i in range(t_last - 1, t - 1):
        s[i] = n
      t_last = t
    n += 1 if dir == '+' else -1
  return s

На самом деле, если вы используете сортировку по основанию или другой алгоритм псевдолинейной временной сортировки, то на практике это становится O (n + m).