Point where maximum intervals overlap 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 &lt; n and j &lt; n:

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

            guests_in += 1

            if guests_in &gt; 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 ?
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] &lt; start:
                heapq.heappop(heap)
                guests -= 1

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

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