#125

Largest Overlap of Intervals

medium

arraysorting

You are given a list of intervals where each intervals[i] = [start, end] is a closed range. Several intervals may cover the same point at once.

Return the largest number of intervals that overlap at any single point — the peak number of simultaneously active intervals. Touching endpoints count as overlapping: [1, 3] and [3, 5] both cover the point 3, so at 3 two intervals are active.

Example

Input: intervals =

Output: 3

At point 3, all three intervals are active, so the peak overlap is 3.

Constraints

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start <= end <= 10^9

Intuition

The answer is the busiest single point, so a first pass picks a set of candidate points — every interval's start is enough — and, for each one, counts how many intervals cover it.

function largestOverlap(intervals) {
  let max = 0;
  // A peak overlap always occurs at some interval's start point.
  for (const [point] of intervals) {
    let active = 0;
    // Count how many intervals cover this candidate point.
    for (const [start, end] of intervals) {
      if (start <= point && point <= end) active++;
    }
    if (active > max) max = active;
  }
  return max;
}

Brute force — for each start point, count covering intervals: O(n²).

Re-counting every interval at every candidate point is O(n²). Can we do better?

The key observation: the active count only ever changes at an endpoint — it ticks up by one when an interval starts and down by one just after one ends. So instead of probing points, turn each interval into two events: a +1 at its start and a -1 at end + 1 (just past the close, so a closed interval is still counted at its own end). Sort all 2n events by position and sweep a running counter; its peak is the answer.

At a tie in position, process the close (`-1`) before the open (`+1`) — an event sitting at end + 1 means that interval is already gone, so it shouldn't be counted alongside one opening there.

Walking it through:

events sorted by position: +1@1, +1@2, -1@6(=5+1), +1@8, -1@9(=8+1), -1@10(=9+1)

sweep↓

+1@1

+1@2

-1@6

+1@8

-1@9

-1@10

+1 → active = 1, max = 1

Process the events for [1,5] and [2,6]. The first start opens an interval; count rises to 1.

+1@1

sweep↓

+1@2

-1@6

+1@8

-1@9

-1@10

+1 → active = 2, max = 2

The second start (from [2,6]) opens while the first is still active — two intervals overlap.

+1@1

+1@2

sweep↓

-1@6

+1@8

-1@9

-1@10

-1 → active = 1

At position 6 the close of [1,5] fires (its end 5, +1). The count drops back to 1; max stays 2.

+1@1

+1@2

-1@6

sweep↓

+1@8

-1@9

-1@10

+1 → active = 2, max still 2

The disjoint interval [8,9] opens. Count returns to 2, but never exceeds the earlier peak.

+1@1

+1@2

-1@6

+1@8

-1@9

sweep↓

-1@10

closes → active = 0

The remaining closes drain the count to 0. The peak seen anywhere was 2 — the answer.

The lane above shows the sorted event stream for [[1, 5], [2, 6], [8, 9]], not the intervals themselves — each cell is a +1/-1 delta at a position, and the sweep pointer accumulates them. The running active count is the number of intervals open at that moment; its maximum over the whole sweep is the largest overlap.

Optimization

Sweep line of endpoints

Split every interval into two events: a +1 at its start (an interval becomes active) and a -1 at end + 1 (it has stopped being active from there on). Modeling the close at end + 1 keeps the closed-interval semantics — an interval ending at x is still counted at x — without any floating-point fudging. Sort the events by position; when two events share a position, process the close (-1) before the open (+1), because an event at end + 1 means the interval is already gone there. Sweep left to right keeping a running count of active intervals and track its maximum.

O(n log n) time (sorting the 2n events dominates), O(n) space for the event list.

function largestOverlap(intervals) {
  // Two events per interval: +1 when it opens, -1 right after it closes.
  const events = [];
  for (const [start, end] of intervals) {
    events.push([start, 1]);   // interval becomes active at start
    events.push([end + 1, -1]); // interval stops being active just past end
  }
  // Sort by position; at equal positions, closes (-1) come before opens (+1)
  // since an event at end + 1 means that interval is already gone here.
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  let active = 0;
  let max = 0;
  for (const [, delta] of events) {
    active += delta;
    if (active > max) max = active;
  }
  return max;
}

Complexity analysis

Time complexity: O(n log n). Here's why:

We build 2n events (a start and an end per interval) — O(n).
Sorting those events by position takes O(n log n).
The final sweep over the sorted events is O(n).

The sort dominates, so the overall time is O(n log n), where n is the number of intervals.

Space complexity: O(n). Here's why:

The event list holds 2n entries — O(n).
The sweep itself keeps only the running count and its max — O(1).

So the extra space is O(n) for the event list; the result is a single integer.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
intervals = []	0	No intervals — peak overlap is 0.
intervals = 15	1	A single interval is active over its whole range.
intervals = 12 34	1	Disjoint intervals never stack — peak is 1.
intervals = 24 47	2	Closed intervals touching at 4 are both active there.
intervals = 110 29 38	3	Fully nested — all three cover the middle at once.
intervals = 15 26 89	2	Two overlap early; the disjoint [8,9] doesn't raise the peak.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor