Coding · Intervals
Maximum Overlapping Intervals
- Reported once
- Medium
- senior SDE
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Given a list of closed integer intervals [start, end] with start never above end, return the largest number of intervals that contain one common point. Intervals that only touch, like [1,4] and [4,6], do share that point. For [[1,4],[2,5],[9,12],[5,9],[5,12]] the answer is 3, because the point 5 lies in [2,5], [5,9] and [5,12]. There are up to 100,000 intervals, they come in no particular order, and an empty list gives 0.
Restated in our own words, not a quote from Myntra or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
The first question is what overlap means at an endpoint. If one interval ends at 4 and another starts at 4, do they overlap? I will assume yes, because the intervals are closed. Then: are the numbers integers or can they be decimals? Can the input be empty, and what should I return? Can start exceed end? Is the list sorted? Do I return only the count, or also where it happens? How many intervals are there, and how large can the coordinates be, since that rules out a counting array over the whole range?
Assumptions: closed intervals, start at most end, unsorted, up to 100,000 intervals, only the count is needed, and coordinates may be large or negative.
Brute force
Say the obvious answer and why it is too slow.
The obvious solution is to try every candidate point. The best point can always be taken to be the start of some interval, so for each interval take its start and count how many intervals contain it. Keep the largest count.
That is simple and correct, but it makes n candidates and counts n intervals for each, so it is O(n²). At 100,000 intervals that is ten billion containment checks, far too slow. A second idea, an array that adds one for every integer covered, depends on the coordinate range instead of n, so it fails when the numbers reach billions. The waste in the first version is that every candidate recounts intervals that are obviously far away.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n log n)
- Space
- O(n)
The pattern is a sweep line over start and end events. Picture a vertical line moving left to right. Its count of open intervals goes up when it reaches a start and down when it passes an end. The answer is the highest the count ever gets.
To do this without events objects, sort the starts and the ends as two separate lists. The ends do not need to stay paired with their starts, because we only count how many intervals are open, not which ones. Then process the starts in order. Before opening the interval at this start, close every interval whose end is strictly smaller than the start. After that, the open count is exactly the number of intervals that contain this point. Add one for the new interval and update the maximum.
Why strictly smaller? Because the intervals are closed. An interval ending at 5 still contains the point 5, so a new interval starting at 5 overlaps it. If the problem used half-open intervals, the test would become less-than-or-equal.
Why is it correct? The maximum overlap happens at some interval's start: if the best point is not a start, slide it left to the nearest start and no interval is lost. At each start, the open count is the number of earlier starts minus the number of ends strictly before it. Every interval that ended before this start must have started before it too, so the subtraction is exact.
Out loud: "Sort starts, sort ends, sweep the starts, retire the ended ones first, and track the peak."
Walk it through
A dry run on the example, step by step.
| Step | Start | Ends retired | Open count | Best so far |
|---|---|---|---|---|
| 1 | 1 | none | 1 | 1 |
| 2 | 2 | none (4 is not < 2) | 2 | 2 |
| 3 | 5 | 4 | 2 | 2 |
| 4 | 5 | none (5 is not < 5) | 3 | 3 |
| 5 | 9 | 5 | 3 | 3 |
Take [[1,4],[2,5],[9,12],[5,9],[5,12]]. The sorted starts are 1, 2, 5, 5, 9 and the sorted ends are 4, 5, 9, 12, 12.
At start 1 nothing has ended, so the open count becomes 1. At start 2 the smallest end, 4, is not below 2, so the count becomes 2. At the first start 5 the end 4 is below 5 and is retired, so the count drops to 1 and the new interval lifts it to 2. At the second start 5 the next end is 5, which is not below 5, so the count rises to 3. That is the peak so far. At start 9 the end 5 retires, giving 2, then 9 is not below 9, and the count rises to 3 again. The answer is 3.
The code
Runnable JavaScript, checked against test cases.
function maxOverlap(intervals) {
const starts = intervals.map((pair) => pair[0]).sort((a, b) => a - b);
const ends = intervals.map((pair) => pair[1]).sort((a, b) => a - b);
let open = 0;
let best = 0;
let endIndex = 0;
for (const start of starts) {
while (ends[endIndex] < start) {
open--;
endIndex++;
}
open++;
best = Math.max(best, open);
}
return best;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Empty list: the loop never runs and the best stays at 0.
- One interval: the count rises to 1, so the answer is 1.
- Touching intervals: an end equal to a start is not retired, so [1,4] and [4,6] count as 2.
- Identical intervals: every copy opens before any ends, so three copies give 3.
- Disjoint intervals: each is retired before the next opens, so the answer is 1.
- Nested intervals: the outer one stays open while the inner ones come and go, adding at most 1 at a time.
- Negatives and large values: only comparisons are used, and the sort uses a numeric comparator.
- Input unchanged: the code builds new arrays for starts and ends.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return the point, or the range of points, where the peak overlap happens?
- How would the loop change if intervals were half-open, so that touching intervals do not overlap?
- How would you answer this for a stream of intervals using a min-heap of end times?
- How would you compute the minimum number of rooms needed for a set of meetings, and is it the same problem?
Where candidates slip
The mistakes this problem punishes.
The most common bug is the endpoint test. Retiring an interval when its end is less than or equal to the next start gives the wrong answer for closed intervals.
- Calling sort without a numeric comparator, so 10 sorts before 9.
- Processing the ends first in a merged event list, which undercounts touching intervals.
- Taking the maximum only when a start is processed but forgetting to retire ended intervals first.
- Assuming the ends must stay paired with their starts, and building a more complicated structure than needed.
- Allocating an array over the full coordinate range, which breaks on large numbers.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.