Алгоритм нахождения наиболее загруженного периода?

Question

У меня есть такие данные:

1: 2 - 10
2: 3 - 15
3: 4 - 9
4: 8 - 14
5: 7 - 13
6: 5 - 10
7: 11 - 15

Я попытаюсь сделать представление более понятным:

        1     2     3     4     5     6     7     8     9     10     11     12     13     14     15
1             |--------------------------------------X---------|
2                   |--------------------------------X--------------------------------------------|
3                         |--------------------------X---|
4                                                  |-X-------------------------------------|
5                                           |--------X------------------------------|
6                               |--------------------X----------|
7                                                                     |---------------------------|

Таким образом, в данном примере 8-9 является критическим периодом, если используется вторая схема, поскольку все точки активны. Какой быстрый и хороший способ решения этой проблемы в Python? Я думаю об использовании динамического программирования, но есть ли другие подходы, которые предлагаются?

Мой подход до сих пор:

Я думал больше с точки зрения реального времени. Итак, всякий раз, когда я получаю новую точку, я делаю это: предположим, что я уже получил 2-10, и я получаю 3-15, затем я выбираю максимум начала и минимума конца, так что в этом случае это 3-10 и увеличиваю счет этого интервала 2. Затем третья точка входит в 4-9, выберите максимальное значение, равное 4, а минимальное значение равно 9, и обновите значение 3-10 до 4-9 и обновите счетчик до 3. Теперь, когда приходит 8-14, я выберите начало этого интервала больше, чем 4-9, а конец этого интервала меньше, чем 4-9. В этом случае это не так, поэтому я создам новое ведро 8-14 и поставлю счетчик на 1. Это не весь алгоритм, но он должен дать общее представление о том, что я здесь делаю. Я посмотрю, смогу ли я набросать псевдокод.

Answer 1

        1     2     3     4     5     6     7     8     9     10     11     12     13     14     15
1             |--------------------------------------X---------|
2                   |--------------------------------X--------------------------------------------|
3                         |--------------------------X---|
4                                                  |-X-------------------------------------|
5                                           |--------X------------------------------|
6                               |--------------------X----------|
7                                                                     |---------------------------|

             +1    +1     +1   +1           +1     +1    -1    -2     +1           -1     -1     -2
              1     2     3     4           5       6    5      3     4             3      2      0
                                                     ^^^^

Получите это?

Так что вам нужно преобразовать это:

1: 2 - 10
2: 3 - 15
3: 4 - 9
4: 8 - 14
5: 7 - 13
6: 5 - 10
7: 11 - 15

в:

[(2,+), (3,+), (4,+), (5,+), (7,+), (8,+), (9,-), (10,-), (10,-), (11,+), (13,-), (14,-), (15,-), (15,-)]

и затем вы просто перебираете счетвверх, когда вы видите + и рассчитывает на -.Самый загруженный интервал будет, когда счетчик максимален.

Так в коде:

intervals = [(2, 10), (3, 15), (4, 9), (8, 14), (7, 13), (5, 10), (11, 15)]
intqueue = sorted([(x[0], +1) for x in intervals] + [(x[1], -1) for x in intervals])
rsum = [(0,0)]
for x in intqueue: 
    rsum.append((x[0], rsum[-1][1] + x[1]))
busiest_start = max(rsum, key=lambda x: x[1])
# busiest_end = the next element in rsum after busiest_start 

# instead of using lambda, alternatively you can do:
#     def second_element(x):
#         return x[1]
#     busiest_start = max(rsum, key=second_element)
# or:
#     import operator
#     busiest_start = max(rsum, key=operator.itemgetter(1))

сложность времени выполнения (n+n)*log(n+n)+n+n или O(n*log(n))

Это также возможнопреобразовать эту идею в онлайн-алгоритм , если у вас нет полного списка интервалов в начале программы, но гарантировано, что входящие интервалы никогда не будут запланированы для прошедшей точки.Вместо сортировки вы будете использовать приоритетную очередь, каждый раз, когда наступает интервал, вы добавляете два элемента: начальную и конечную точки, каждая из которых имеет +1 и -1 соответственно.А потом вы выскакиваете, считаете и отслеживаете час пик.

Answer 2

Я бы начал думать о занятости точки x как о количестве активаций слева от x, минус количество деактиваций слева от x. Я бы отсортировал активации и деактивации по времени, в которое они происходят (за время O (nlog (n))). Затем вы можете просмотреть список, отслеживая число активных (y), увеличивая и уменьшая этот номер с пройденными активациями и деактивациями. Самым загруженным периодом будут точки, в которых у максимален. Я не могу придумать решение с моей головы, которое лучше O (nlog (n)). Грубая сила была бы O (n ^ 2).

Answer 3

Вот то, что я думал о подходе, основанном на бинах, и адаптирован для обработки добавлений динамически, в основном то, что Р.К. говорил, что я верю.

from collections import defaultdict
from operator import itemgetter

class BusyHour(object):
    def __init__(self):
        self.pairs = defaultdict(int)
    def add_period(self, period):
        start, end = period
        for current_period in range(start, end):
            pair_key = (current_period, current_period + 1) 
            self.pairs[pair_key] += 1
    def get_max(self):
        # sort, defaults to smallest to largest
        # --> items() returns (key, value) pairs
        # --> itemgetter gets the given index of the first argument given to sorted
        return max(self.pairs.items(), key=itemgetter(1))


if __name__ == '__main__':
    periods = [(2, 10), (3, 15), (4, 9), (8, 14), (7, 13), (5, 10), (11, 15)]
    bh = BusyHour()
    for period in periods:
        bh.add_period(period)
    print bh.get_max()

Обновлено : сортировать только по вызову get_max и использовать defaultdict (int).

Answer 4

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

Однако это не сработает сразуне пересекаетсяВозможно, вы сможете добавить дополнительную логику, чтобы покрыть это, поэтому я опубликую то, что я думал:

>>> periods = [(2, 10), (3, 15), (4, 9), (8, 14), (7, 13), (5, 10),]
>>> intersected = None
>>> for first, second in periods:
...     if not intersected:
...         intersected = set(range(first, second + 1))
...     else:
...         intersected = intersected.intersection(set(range(first, second + 1)))
...
>>> intersected
set([8, 9])

Примечание: это не включает период 11-15.Вероятно, лучше всего создавать пары бинов, как указано в RK

Answer 5

Не уверен, что понимаю ваш вопрос.Если вы пытаетесь найти наиболее распространенный «интервал», вы можете суммировать их за интервал.Таким образом, у вас есть 12 сегментов для приведенного выше примера.Для каждого использования вы добавляете 1 к каждому из сегментов, используемых в данном конкретном случае, и в конце находите максимальное значение во всех сегментах.Здесь это будет 6 для интервала 8-9.