Given an array of intervals, determine the maximum number of intervals that overlap at any point. Each interval is half-open, meaning it includes the start point but excludes the end point.

Example:

Input: intervals = [[1, 3], [5, 7], [2, 6], [4, 8]]
Output: 3

Constraints:

• The input will contain at least one interval.

• For every index i in the list, intervals[i].start < intervals[i].end.

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition

Think about what it means when x intervals overlap at a certain point in time. This means at this point, there are x “active” intervals, where an interval is active if it has started but not ended.

In the example below, we see three active intervals at time 5 (intervals that started at or before this time, and haven’t yet ended):

To find the number of active intervals at any point in time, we need to identify when an interval has started and when an interval has ended. The start point of an interval indicates the start of a new active interval, whereas an end point represents an active interval finishing. This suggests an approach which looks at start and end points individually could be useful. Let’s explore this idea further.

Processing start points and end points
Let’s step through each point in the array of intervals in chronological order, and see if we can determine the number of active intervals at each point.

The first point is a start point, indicating the start of the first active interval. So, let’s increment our counter:

The next point is another start point. This is the start of the second active interval, so let’s increment our counter again. Now, the number of active intervals is 2, which correctly corresponds with the number of overlapping intervals at this point:

The next point is an end point, which means an active interval has just finished. So, let’s decrement our counter. Now, the number of active intervals is 1, which also corresponds with the current number of overlapping intervals:

We’ve now rationalized what we need to do whenever we encounter a start point or end point:

• If we encounter a start point: increment active_intervals.
• If we encounter an end point: decrement active_intervals.

Processing the remaining points allows us to attain the number of active intervals at each point. The final answer is obtained by recording the largest value of active_intervals.

Edge case: processing concurrent start and end points
An edge case to consider is when a start and end point occur simultaneously:

Which point should we process first? Keep in mind the value of active_intervals is 3 right before we reach time = 6 in the above example.

At time 6, if we process the start point first and increment active_intervals, we would update it to 4 first, which is incorrect as there are never 4 active intervals at this moment. This is an issue because our final answer is the largest value of active_intervals encountered, which means we’ll incorrectly record 4 as the answer.

If we process the end point first, we won’t encounter this issue:

Therefore, for start and end points that occur simultaneously, we should process end points before start points.

Iterating over interval points in order
We need a way to iterate through the start and end points in the order they should be processed. To do this, we can combine all start and end points into a single array and sort it. For start and end points of the same value, we ensure end points are prioritized before start points while the points are being sorted.

Let’s use ‘S’ and ‘E’ to differentiate between start and end points, respectively:

The algorithm we used to solve this problem is known as a ‘sweeping line algorithm.’ It works by processing the start and end points of intervals in order, as if a vertical line was sweeping across them. This method efficiently handles the dynamic nature of interval overlaps by specifically focusing on start and end points, rather than individual intervals.

Implementation

from typing import List
from ds import Interval
    
def largest_overlap_of_intervals(intervals: List[Interval]) -> int:
   points = []
   for interval in intervals:
       points.append((interval.start, 'S'))
       points.append((interval.end, 'E'))
   # Sort in chronological order. If multiple points occur at the same time, ensure
   # end points are prioritized before start points in the sorting order.
   points.sort(key=lambda x: (x[0], x[1]))
   active_intervals = 0
   max_overlaps = 0
   for time, point_type in points:
       if point_type == 'S':
           active_intervals += 1
       else:
           active_intervals -= 1
       max_overlaps = max(max_overlaps, active_intervals)
   return max_overlaps

int largestOverlapOfIntervals(vector<Interval>& intervals) {
    vector<pair<int,int>> points;                  // (time, type) 0 = End, 1 = Start
    for (auto& iv : intervals) {
        points.push_back({iv.start, 1});
        points.push_back({iv.end, 0});
    }
    sort(points.begin(), points.end());            // ties: End(0) before Start(1)
    int active = 0, best = 0;
    for (auto& p : points) {
        if (p.second == 1) {    // a Start adds one active interval
            active++;
        } else {                // an End removes one
            active--;
        }
        best = max(best, active);
    }
    return best;
}

int largestOverlapOfIntervals(List<Interval> intervals) {
    List<int[]> points = new ArrayList<>();       // {time, type} 0 = End, 1 = Start
    for (Interval iv : intervals) {
        points.add(new int[]{iv.start, 1});
        points.add(new int[]{iv.end, 0});
    }
    points.sort((p, q) -> p[0] != q[0] ? p[0] - q[0] : p[1] - q[1]);
    int active = 0, best = 0;
    for (int[] p : points) {
        if (p[1] == 1) active++; else active--;
        best = Math.max(best, active);
    }
    return best;
}

Complexity Analysis

Time complexity: The time complexity of largest_overlap_of_intervals is $O(n\log(n))$, where $n$ denotes the number of intervals. This is because we sort the points array of size $2n$ before iterating over it in $O(n)$ time.

Space complexity: The space complexity is $O(n)$ due to the space taken up by the points array.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.

The same steps in each language