如何使这段代码的时间复杂度更快

Question

我需要做一个代码，它包含两个元组，比如[（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()

Answer 1

如果N是事件数。你知道吗

在线性时间O（N）中，您可能可以在日历矩阵中用1（或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）是您的日期。你知道吗

祝你好运。你知道吗