最大间隔重叠点

Question

我正在解决极客的“点最大间隔重叠”问题，为极客，https://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/。按照本文中的解决方案，我使用了两个列表来存储间隔的开始和结束时间。这是我在Python中的解决方案：

def maxIntervalOverlap(intervals):

    # break intervals into two lists
    first = lambda x: x[0]
    end = lambda x: x[1]

    enter = list(map(first, intervals))
    exit = list(map(end, intervals))

    # sort lists
    enter.sort()
    exit.sort()

    i = 1
    j = 0
    time = enter[0]

    n = len(enter)

    max_guests = 1
    guests_in = 1

    # process events in sorted order
    while i < n and j < n:

        # next event is arrival, increment count of guests
        if enter[i] <= exit[j]:

            guests_in += 1

            if guests_in > max_guests:
                max_guests = guests_in
                time = enter[i]

            i += 1

        else:
            guests_in -= 1
            j += 1

    print(f"Point where maximum number of intervals overlap is {time}")

下面是一个测试用例

intervals = [[1, 4], [2, 5], [10, 12], [5, 9], [5, 12]]
maxIntervalOverlap(intervals)

我如何解决这个问题而不必创建额外的两个列表？

Answer 1

这里有一个解决方案，它只使用一个额外的数据结构。我使用heapq库来维护一个堆，在这里可以很容易地检查最小的项并在不再需要时删除它。您还可以使用美妙的SortedList库中的分类容器。

其基本思想是循环按开始时间排序的间隔。如果某些时间间隔具有相同的开始时间，则按结束时间对这些时间进行排序。幸运的是，Python的sort()方法或sorted()函数将处理这个问题。

对于每个开始-结束间隔，结束时间保存在堆中。

对于堆中任何比当前启动时间早的结束时间，我们减少了来宾的数量，并从堆中删除了结束时间。

开始时间代表客人的到达，因此增加客人的数量并检查是否是新的最大人数。

在最后的开始时间之后，客人的数量只能减少，所以我们不需要处理任何剩余的结束时间。

以下是代码：

import heapq

    def maxIntervalOverlap(intervals):
        guests = 0
        maxguests = 0
        maxtime = None

        heap = []

        for start, end in sorted(intervals):
            heapq.heappush(heap, end)

            # handle intervals that ended before 'start' time
            while heap[0] < start:
                heapq.heappop(heap)
                guests -= 1

            # add the guest that just arrived at 'start' time
            guests += 1
            if guests > maxguests:
                maxguests = guests
                maxtime = start

        print(f"Time with maximum guests is {maxtime}.")