Как сделать этот код за более короткое время? - PullRequest
Новая
       9

Как сделать этот код за более короткое время?

0 голосов
/ 10 декабря 2018

Мне нужно сделать код, который принимает список с кортежами с двумя числами, такими как [(1, 2), (5, 8), (1, 3), (1, 1), (3, 6)].Первое число кортежа - это день начала события, а второе число - день его окончания.Этот код должен возвращать наибольшее количество событий, происходящих одновременно, а сложность времени должна быть O (n).Что у меня есть проблема, это сложность времени.Это наименее сложный код времени, который я мог бы написать: 

def divide_to_groups(calendar):
    if len(calendar) == 0:
        return 0

    def group_num(j, groups):    # takes index of group and list groups, returns last number of last tuple
        if isinstance(groups[j][-1], int):
            return groups[j][-1]
        else:
            return groups[j][-1][1]

    calendar = list(sorted(calendar))
    groups = [[calendar[0]]]

    for i in range(1, len(calendar)):

        for j in range(len(groups)):

            if group_num(j, groups) < calendar[i][0]:   # if previous group has time when current event begins
                groups[j].append(calendar[i])

                break
            elif j+1 == len(groups):
                groups.append([calendar[i]])

    return len(groups)

# Tests
def test_default():
    calendars = [
        [ ],
        [ (1, 2), (3, 3), (500, 800), (50, 56) ],
        [ (1, 2), (5, 8), (1, 3), (1, 1), (3, 6) ],
        [ (1, 1), (1, 50), (25, 75), (60, 100), (2, 3) ]
    ]

    answers = [ 0, 1, 3, 2 ]

    for i in range(len(calendars)):
        result = divide_to_groups(calendars[i])
        if result == answers[i]:
            print("[", i, "] OK.", sep="")
        else:
            print("[", i, "] Not OK. Expected ", answers[i], " but got ", result, ".", sep="")


if __name__ == '__main__':
    test_default()

1 Ответ

0 голосов
/ 10 декабря 2018

Если N - ваше количество событий.

В линейном времени O (N) вы, вероятно, можете заполнить свои диапазоны в календарной матрице единицами (или знаком X), где столбцы будутдней и суммируйте каждый столбец, чтобы увидеть, сколько событий в день D. 

           1 2 .... 31
event1     x x x .....
event2       x x x ...
event3       x x .....
...
-----------------------
SUM        1 4 5 .....

А затем вычислите максимальный индекс i, где SUM(D=i) является максимальным.

Вы можете даженапишите список sums(d) напрямую, не сохраняя его в промежуточной матрице, просто используя ваши структуры диапазона.

Еще одна проблема, которую следует рассмотреть, - это кодирование дня года в столбце.Библиотеки дат обычно указывают, какой день года (1 <= d <= 366) ваша дата. </p>

Удачи.

...