Platform Placing

This problem gives us fixed "anchor points" on the x axis, and a minimum and maximum interval which we can carve out around those anchor points, and asks what the maximum non-overlapping coverage ove the axis is.

We can first consider the two-anchor case. Suppose we have two anchors which would overlap if they both had maximum widge intervals. We can also see that so long as those segments are grown to such a degree that they are touching, then the total span of the two intervals will be the same, regardless of the size of each individual one. Given that fact, we can choose to shift those pair of platforms to the left or right, such that they are still touching. If we consider a third anchor to the right of the original two, we can see that we get no advantage of placing the first to platforms further right than necessary, as it can only impede the growth of the third.

This leads to a straightforward greedy solution:

• place a minimum widge platform on every anchor
• grow the left-most platform until it either reaches max width, or bridges to the next platform
• repeat with all subsequent platforms, insuring to occur that growing them would not impede an earlier platform