Какой эффективный способ получить максимальный параллелизм в списке кортежей? - PullRequest
Новая
       22

Какой эффективный способ получить максимальный параллелизм в списке кортежей?

2 голосов
/ 08 февраля 2020

Я пытался решить эту проблему эффективным способом. Проблема:

Постановка задачи

Приведен список кортежей в форме [(start1, end1), (start2, end2), (start3, end3)....(startn, endn)], где start и end - положительные целые числа. Каждый кортеж должен представлять временное окно, например: [(1, 3), (73, 80)...]. Найдите время (целое число), в котором происходит максимальный параллелизм, и получите кортежи, где происходит максимальный параллелизм.

Ограничения:

  1. start и end являются целыми числами времени и находятся между От 0 до n
  2. Для всех случаев start <<code>end
  3. start включительно, но end исключительно
  4. Для времени (целого), где максимум происходит параллелизм, мы можем получить только один, если есть несколько случаев

Например, приведенное ниже расписание будет иметь max_concurrency во время 2, а кортежи будут (0,3), (2,3), ( 1, 200), которые имеют его. 

schedule = [
            (0, 3),
            (3, 5),
            (2, 3),
            (6, 8),
            (10, 12),
            (73, 92),
            (1, 200),
            ]

Мой код

На время, когда происходит максимальный параллелизм. Поправьте меня, если я ошибаюсь, но я думаю, что это работает в O(n^2) раз. 

from collections import defaultdict

schedule_dict = defaultdict(lambda: 0)

for start, end in schedule:
    for time in range(start, end):
            schedule_dict[time] += 1

max_concurrency = max(schedule_dict, key=schedule_dict.get)
print(f"Time where max concurrency happens is : {max_concurrency}")

Выход 

Time where max concurrency happens is : 2

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

Мой код 

for start, end in schedule:
    if start <= max_concurrency < end:
        print(f"{(start, end)}")

Вывод 

(0, 3)
(2, 3)
(1, 200)

Наконец-то мой вопрос

Какой более эффективный способ сделать это, чтобы уменьшить сложность времени и пространства?

1 Ответ

1 голос
/ 08 февраля 2020

Число интервалов, перекрывающихся в любой момент времени T, - это число времен начала интервала, меньшее или равное T, за вычетом количества времен окончания интервала, меньшего или равного T.

  1. Put время начала и время окончания в отдельных списках и сортируйте их.
  2. Инициализируйте счетчик глубины на 0
  3. Пройдите по спискам по порядку (как сортировка слиянием), добавив 1 для каждого времени начала и вычитая 1 для каждого конечного времени
  4. Помните, когда счетчик достигает максимума - это время максимального перекрытия.

Вот реализация в python: 

schedule = [
  (0, 3),  (3, 5), (2, 3), (6, 8),
  (10, 12), (73, 92), (1, 200),
  ]

starts = [x[0] for x in schedule]
ends = [x[1] for x in schedule]

starts.sort()
ends.sort()

endpos = 0
depth = 0
maxdepth = 0
maxdepthtime = -1

for time in starts:
    depth+=1
    while endpos < len(ends) and ends[endpos]<= time:
        depth -= 1
        endpos += 1
    if depth > maxdepth:
        maxdepth = depth
        maxdepthtime = time

overlappers = [x for x in schedule
    if (x[0] <= maxdepthtime and x[1] > maxdepthtime)]

print ("Max overlap at time: ", maxdepthtime, " depth ", maxdepth)
print ("Intervals: ", overlappers)
...