Understanding maximum overlap pattern

For some problems, we need to find the maximum number of overlapping intervals from a list of intervals. There are a few brute-force solutions to this problem using nested loops, but all of them are complicated and inefficient. For problems like these, we can treat the start and end coordinates of all intervals as individual points on the x-axis of a Cartesian plan and use the line sweep technique to find the maximum number of overlapping intervals in a single pass.

In this lesson, we will learn more about using the line sweep technique to find the maximum number of overlapping intervals from a list of intervals.

Maximum overlapping intervals

Consider we are given an array of intervals arr where each item in the array is a pair of an interval's start and end coordinates. 

To find intersecting intervals, we must separate the start and end coordinates and store them in a single array. We create an array points that will store all coordinates from arr along with their identification as start or end. We initialize points by traversing arr and appending each interval's start and end coordinates along with a flag denoting if it is an interval start or end.

Finally, we sort the pointsarray in ascending order of values. If a start point and end point have the same value, we keep the end point before the start. This is because we will not count two intervals as overlapping if one interval starts at the same time as the other ends. As we will see later, when we sweep the line from left to right, keeping the end before the start, in this case, ensures we process the closing of an interval before opening the next.

Now, we create a counter variable overlap to count the overlapping intervals at any point and initialize it with 0. We also create another variable maxOverlap to keep track of the maximum intersecting intervals seen so far and initialize it with 0. We then traverse the points array, and every time we reach a start coordinate, it means some interval starts at this point, so we increment overlap by one. Similarly, every time we see an end coordinate, we decrement overlap by one. Throughout the traversal, we compare the current value of overlap with the maxOverlap and update it if needed.

This way, at the end of the traversal, maxOverlap will have the maximum overlapping intervals at any point. It takes at least two intervals for an overlap, and so, if the value of maxOverlap is less than 2, we set it to 0 as it means all intervals were non-overlapping.

Algorithm

The algorithm given below outlines the generic algorithm to find the maximum overlapping intervals in an array of intervals.

• Step 1: Create a dynamic array `points` and store start and end points intervals in the array.
• Step 2: Sort the `points` array in non-decreasing order. If start and end points have the same value, end points should come before start.
• Step 3: Initialize two variables `overlap` and `maxOverlap` to 0 that will keep track of the current overlap and maximum overlap seen so far.
• Step 4: Iterate in `points` and do the following
  • Step 4.1: If the current point is a start point, increment `overlap` and update `maxOverlap` if needed.
  • Step 4.2: If the current point is an end point, decrement `overlaps`.

Implementation

Given below is the generic code implementation to find the maximum number of intersecting intervals in an array of intervals.

Complexity Analysis

To find the maximum number of overlapping intervals, we separate the start and end coordinates of all intervals in arr and add them to the points array. The points array will have a size of 2*N where N is the size of the input array, so sorting it takes O(NlogN) time. We only traverse the points array after that, which takes linear O(N) time, so the time complexity is O(NlogN) in any case.

Since we create an additional points array to store the coordinates of all intervals in any case with a size of 2*N, the space complexity in any case is O(2*N) ~ O(N).

Best Case:

• Space Complexity - O(N)
• Time Complexity - O(NlogN)

Worst Case:

• Space Complexity - O(N)
• Time Complexity - O(NlogN)