912. Every Event You Can Attend

Event i runs from day s[i] to day e[i] inclusive, and you may attend it on ANY single day in that range. You attend at most one event per day. Print the largest number of events you can attend.

``` events (1,2) (2,3) (3,4) -> 3 one on each of days 1, 2, 3

events (1,4) (4,4) (2,2) (3,4) -> 4 day 2 for (2,2), day 3 for (3,4), day 4 for (4,4), day 1 for (1,4)

events (1,1) (1,1) (1,1) -> 1 three events, one day ```

## What most people try first

Sorting by start and attending greedily is wrong: an event starting early but running for a long time should be left for later, and the second example above defeats it.

Sorting by end and attending each event on its first free day is right in spirit, but "first free day" then needs a search, and scanning days for each event is O(n * days), which is 10^10 at the limits here.

## The method: sweep the days, not the events

Walk the days in increasing order. On each day, every event that has STARTED is a candidate, and the right one to attend is whichever candidate ROTS FIRST, that is, has the smallest end day.

sort events by start h = empty min-heap of end days, i = 0, attended = 0 for day = smallest start upward: push the end day of every event whose start equals day discard from the top of h every entry whose end day is < day if h is not empty: pop one; attended = attended + 1 print attended

The discarding is LAZY DELETION. An event whose window closed is not hunted down at the moment it expires; it sits in the heap until it reaches the top, and then it is thrown away. A heap has no "find and remove this entry" that is better than O(n), so paying once per entry when it surfaces is strictly cheaper than paying to locate it.

## Why earliest-ending is optimal

The exchange argument. Suppose an optimal plan attends event B on day d while event A is also available on d and ends strictly earlier than B.

If the plan never attends A, swap: attend A on d instead of B. The count is unchanged and the plan is still valid, because A was available on d.

If the plan attends A on some later day d', then d' <= end(A) < end(B), so d' is inside B's window too, and d' > d >= start(B). Swap the two days: attend A on d and B on d'. Both remain legal and the count is unchanged.

So some optimal plan agrees with the greedy on day d, and repeating the argument day by day shows the greedy is optimal throughout.

## The boundary that breaks a careless implementation

Expiry is end < day, not end <= day. An event ending on day d may still be attended on day d. Getting this wrong loses exactly the events that finish today, which is a class of input small tests often miss.

The loop must not run over every integer from 1 to the largest end day when the heap is empty and no event has started; it should jump to the next start. With the day range capped at 10^5 here a plain loop is also fine, and the jump is the habit that makes the same code survive a range of 10^9.

## Overflow

Nothing here exceeds 10^5. The answer is at most n, days are at most 10^5, and no product or sum is formed. A 32-bit integer is ample, and there is no overflow lesson in this problem.

## Related problems

Problem #1036 takes the most meetings from a set where each meeting occupies its WHOLE interval, and there sorting by end and walking once is the entire answer with no heap. The difference is that a meeting blocks its whole range while an event here consumes only one day of it, which is what turns a single sorted walk into a day-by-day sweep with a live candidate set. Problem #1437 is the same whole-interval question phrased as removals.

## Cost

Time O(n log n + T) where T is the span of days touched. Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ s[i] ≤ e[i] ≤ 100000`