Painting the Floodwall

This problem asks, given a set of ranges, what is the subset with the maximal total range size (sum of size of each of the ranges) with the restriction ranges do not overlap?

This is a scheduling problem where each task must run in a specified time slot. Since tasks are assigned an exact slot, the standard greedy algorithm (earliest deadline) does not apply. We also realize that other greedy algorithms are likely to fail (greedily taking any given task could prevent us from taking a better task later!). This screams DP.

It's a knapsack-like DP, but is a single dimension. Note that it has to be given the size of the input (200k items).

It's easy to see how the dp works:

dp(x) = max:

• dp(x+1) (don't have a mural, or choose not to paint)
• d + dp(x+d) for each mural that starts at x

The runtime is O(x+m), where x is < 10^18.....oh wait...that's too slow.

It's easy to see the fix here. We only have 200k murals, so that means we only have 200k relevant x points. So sort all the mural start and ends and create a mapping. now x is bounded by 200k. Tada.