1
\$\begingroup\$

I am solving the "Point where max intervals overlap" problem on geeks for geeks, https://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/. Following the solution in the article, I used two lists to store start and end times of the intervals. This is my solution in 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}")

and below is a test case

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

How can I solve this problem without having to create the two extra lists ?

\$\endgroup\$
2
  • \$\begingroup\$ Please include the challenge description in the question itself. Links can rot. \$\endgroup\$
    – Mast
    Commented May 22, 2020 at 20:29
  • \$\begingroup\$ You could take a look at interval trees. They would work quite differently though. For example, duplicate intervals are not allowed, and the interval end is not counted, i.e. \$ [a, b) \$. \$\endgroup\$
    – Alex Povel
    Commented May 22, 2020 at 21:14

1 Answer 1

2
\$\begingroup\$

Here's a solution that only uses one extra data structure. I use the heapq library to maintain a heap, where it easy to check the smallest item and remove it when it's not needed any longer. You could also use SortedList from the wonderful sortedcontainers library.

The basic idea is to loop over the intervals sorted by start time. If some intervals have the same start time, then sort those by end time. Fortunately, Python's sort() method or sorted() function will take care of that.

For each start-end interval, the end time is saved in the heap.

For any end times in the heap that are earlier than the current start time, we reduce the number of guests and remove the end time from the heap.

The start time represents the arrival of a guest, so increment the number of guests and check if it is a new maximum number.

After the last start time, the number of guests can only decrease, so we don't need to process any left over end times.

Here is the code:

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}.")
\$\endgroup\$
1
  • \$\begingroup\$ Thanks ! That is the solution I was looking for. \$\endgroup\$ Commented May 25, 2020 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.