Алгоритм поиска самого загруженного периода?

Ответ 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 соответственно. И затем вы выскакиваете и считаете и отслеживаете пиковый час.

Ответ 2

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

Ответ 3

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

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

>>> 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. Вероятно, вам лучше всего просто создать пары bin, упомянутые R.K.

Ответ 4

Вот то, что я думал о методе, основанном на бен, и адаптировано для динамического добавления добавляет динамически, в основном, что R.K. говорил, что я верю.

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

Ответ 5

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