725. The Year the Most People Were Alive

Each person is given by a birth year b and a death year d, and counts as alive in every year from b up to d - 1 inclusive. Print the EARLIEST year with the most people alive.

Years run from 1 to 3000.

(1950 1961) (1960 1971) (1955 1960) -> 1955 (2 3) (2 3) (1 4) -> 2 (3 4) (1 2) -> 1

## Counting people is the wrong loop

Asking "who is alive in year y" for every year costs O(people * years). Nothing about a person needs to be examined more than twice.

## One increment and one decrement per person

Sweep over years, carrying a running count of who is currently alive. A person changes that count exactly twice: up when they are born, down when they die.

diff[b] += 1 diff[d] -= 1

Then one pass over the years accumulates the count and keeps the best.

This is the difference array of problem 721, applied to an index that is not an array position but a YEAR. Seeing that the technique works over any ordered index, not just array positions, is the point of putting it here.

## The half-open interval is the whole difficulty

Alive means b .. d - 1, not b .. d. So the decrement goes at d, not d + 1.

Placing it at d + 1 counts everyone as alive in their year of death. On (1950 1961) (1960 1971) (1955 1960) that turns the answer from 1955 into 1960, because the third person would still be counted alongside the other two.

Reading "up to d - 1" off the statement and translating it into "decrement at d" is the step to get right, and it is one of the most common interview slips with this technique.

## Earliest, not just largest

The comparison must be STRICTLY greater when updating the best, so an equal count later in the sweep does not replace an earlier year.

Using >= returns the LAST such year instead, and on (1 5) (1 5) (1 5) that is 4 rather than 1.

## Cost

Time O(people + years). Space O(years).

Constraints - `1 ≤ m ≤ 200000` - `1 ≤ b < d ≤ 3000`