1481. The Most Airtime You Can Keep

n programmes are offered. Programme i occupies the HALF-OPEN stretch [a, b) with a < b. You may keep any set of programmes provided no two of them overlap; programmes that merely TOUCH, one ending exactly where the next begins, may both be kept.

Print the largest total airtime you can keep, where a programme contributes b - a.

[1,5) [2,6) [8,9) [3,4) -> 5 [1,3) [3,5) [5,7) -> 6 [0,10) [1,4) [5,9) -> 10

The middle line is the endpoint rule. The three programmes touch and never overlap, so all three may be kept, for 2 + 2 + 2 = 6. Under a CLOSED reading no two of them could be kept together and the answer would be 2.

## What most people try first

The activity-selection greedy: sort by end and keep every programme that starts at or after the last kept one. That maximises the COUNT and not the total, and the two are different objectives. On [1,2) [1,9) [3,4) [5,6) [7,8) it keeps four short programmes for a total of 4, where keeping [1,9) alone gives 8. That input is in the tests.

The other plausible rule is to take the LONGEST programme that still fits, then the next longest, and so on. On [0,7) [0,4) [4,10) that takes [0,7) for a total of 7, where [0,4) and [4,10) give 10. Neither greedy survives, which is what makes this a table rather than a sweep.

## Sort by end, then take or skip each programme

sort the programmes by b, ascending ends[i] = the end of the i-th programme in that order dp[0] = 0 for i in 1 .. n: (a, b) = programme i j = how many programmes among the first i-1 have end <= a binary search dp[i] = max(dp[i-1], (b - a) + dp[j]) answer = dp[n]

O(n log n): one sort plus one binary search per programme.

## Why the recurrence is complete

dp[i] is the best total using only the first i programmes in end order. Consider the best such set. Either it leaves programme i out, in which case it is a set over the first i - 1 and worth dp[i-1], or it keeps programme i, in which case every other member ends at or before a, because it must not overlap [a, b) and it ends no later than b. Those members are exactly the programmes counted by j, so the rest is worth at most dp[j], and the total is (b - a) + dp[j]. Both cases are achievable, so the maximum of the two is exact.

Sorting by END is what makes the set of compatible earlier programmes a PREFIX of the order, which is what lets one number dp[j] stand for all of them. Sorting by start would not: the programmes compatible with i would be scattered through the order.

## The boundary that breaks a careless implementation

The binary search looks for ends <= a, non-strict, because touching is allowed. Using < a forbids a programme from following one that ends exactly where it starts, and the middle sample then answers 4 instead of 6.

Ties on b may be broken any way: two programmes with the same end overlap each other whenever both are non-empty, so at most one of them is ever kept, and the recurrence considers each in turn.

## Overflow

The kept programmes do not overlap, so their total is at most the span 10^9 - (-10^9) = 2 * 10^9. A signed 32 bit integer holds 2147483647, so that FITS, with about 147 million to spare. The intermediate b - a is at most 2 * 10^9 as well. Keeping the table in 64 bit costs nothing and removes the question.

## Related

Problem 1437 removes the fewest intervals so that none of the rest overlap, which is the same as keeping the MOST intervals and is answered by the greedy this problem defeats. Problem 468 attaches an arbitrary profit to each interval, where the same table applies with the profit in place of the length. This one derives the value from the interval itself, which is what makes the longest-first greedy so tempting.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a < b ≤ 10^9` - each programme occupies the half-open stretch `[a, b)`, so one ending at `t` and one starting at `t` may both be kept - programmes arrive in no particular order and may repeat