Maximum Concurrent Intervals Over a Small Integer Range
You are given a very large list of intervals, each with an integer start and end time. You want the maximum number of intervals active at the same instant (the peak overlap).
The catch: the array of intervals is extremely long, so sorting it is undesirable, BUT the start and end times are confined to a relatively small integer range $[0, T]$.
How do you find the maximum overlap efficiently given that structure?
Hints
- The standard sort-and-sweep is $O(n\log n)$ -- but you are told the time range is small, which is a hint to avoid sorting.
- Use a difference array: add $+1$ at each start index and $-1$ just after each end index.
- Prefix-sum the difference array; the running total at each time is the active count, and its maximum is the answer.
Worked Solution
How to Think About It: The usual meeting-rooms solution sorts all endpoints and sweeps, costing $O(n \log n)$. But here you are told two things: $n$ is huge (so the $\log n$ sort hurts) and the time values live in a small range $[0, T]$. That is the signal to use a difference array (bucket counting) and skip sorting entirely -- the work becomes $O(n + T)$.
Difference array (sweep line by counting): 1. Allocate diff of size $T+2$, all zeros. 2. For each interval $[s, e]$: do diff[s] += 1 and diff[e+1] -= 1 (use $e+1$ if the end is inclusive; use $e$ if intervals are half-open -- match the spec). 3. Take the running prefix sum over diff; the value at time $t$ is the number of intervals active at $t$. 4. The answer is the maximum prefix-sum value.
Code: ```python def max_overlap(intervals, T): diff = [0] * (T + 2) for s, e in intervals: diff[s] += 1 diff[e + 1] -= 1 # inclusive end best = cur = 0 for t in range(T + 1): cur += diff[t] best = max(best, cur) return best ```
Complexity: $O(n + T)$ time and $O(T)$ space -- no sorting. When $T \ll n \log n$, this is a clear win, and it streams: you can apply the increments as intervals arrive.
If the range were large and sparse instead, you would fall back to sorting endpoints (or a hash map of just the touched times) and sweeping -- but the small-range hint is precisely what makes the diff-array bucket approach optimal here.
Answer: Use a difference (delta) array over $[0,T]$: $+1$ at each start, $-1$ just past each end, prefix-sum, and take the max. $O(n + T)$, no sort.
Intuition
This is the classic 'maximum number of overlapping intervals' problem, but the interviewer's twist -- huge $n$, small value range -- is steering you from comparison sorting to counting sort's cousin, the difference array. The delta-array trick converts $n$ range updates into $n$ point updates plus one linear pass, the same idea as a 1D prefix-sum sweep line. Recognizing when the value domain is small enough to bucket directly (turning $O(n\log n)$ into $O(n+T)$) is a core optimization instinct; the fallback for a large sparse range is to sort or hash only the endpoints that actually occur.