# 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 < 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 ?

• Please include the challenge description in the question itself. Links can rot.
– Mast
Commented May 22, 2020 at 20:29
• 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)$. Commented May 22, 2020 at 21:14

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}.")

• Thanks ! That is the solution I was looking for. Commented May 25, 2020 at 0:49