1484. The Cheapest Way to Cover Every Position

Whole positions 0 to T must all be covered. n contracts are offered; contract i covers the CLOSED range of positions [l, r] with l <= r and costs c. Two contracts that are ADJACENT over the positions, one ending at p and the next beginning at p + 1, leave nothing uncovered between them.

Print the smallest total cost of a set of contracts covering every position from 0 to T, or -1 if no set does.

T=9, [0,4] cost 1, [5,9] cost 1 -> 2 T=9, [0,4] cost 1, [6,9] cost 1 -> -1 T=5, [0,5] cost 10, [0,2] cost 3, [3,5] cost 3 -> 6

The first line is the adjacency rule. [0,4] and [5,9] share no position and yet positions 0 through 9 are all covered, because there is no whole number between 4 and 5. The second line leaves position 5 bare, so nothing works. The third line is the whole point of the problem: the single contract covering everything costs 10, and two cheaper contracts covering the same positions cost 6 between them.

## What most people try first

The greedy from problem 1473: keep a frontier and always take the contract reaching FURTHEST from it. That is optimal when every contract costs the same, and it is wrong here. On the third line it takes [0,5] for 10, since that reaches furthest from position 0, and stops: cost 10 where 6 is possible.

Nor does taking the cheapest usable contract work. On T=6 with [0,6] cost 100, [0,3] cost 1 and [2,6] cost 1, the cheapest usable contract at the frontier is a tie between the two ones, and picking [0,3] then [2,6] costs 2, which happens to be right; but the rule is cheapest-first rather than reach-first, and a contract that is cheap and short can strand the frontier where nothing affordable continues. With costs attached, no single local criterion survives, because a contract must be judged on cost AND reach at the same time and those trade off.

## A shortest-path table over the frontier

Let g[x] be the cheapest way to have covered positions 0 through x - 1, so g[0] = 0 and the answer is g[T + 1].

g[0] = 0; every other g[x] = infinity for x from 0 to T: if g[x] is infinity: continue for each contract [l, r] of cost c with l <= x <= r: y = min(r + 1, T + 1) g[y] = min(g[y], g[x] + c) answer = g[T + 1], or -1 if it is still infinity

Every relaxation moves strictly forward, because r >= x gives r + 1 > x, so one sweep of x in increasing order settles the table: there is no need for a priority queue. The cost is O(n T), about 4 * 10^6 steps at the limits.

## Why the state is the frontier and nothing else

A set of contracts covers 0 .. x - 1 with no gaps if and only if, listed in order, each one starts at or before the position just after the previous one ended. So the only thing the past needs to tell the future is how far the covering has reached; WHICH contracts achieved it makes no difference to what can follow. That is exactly the condition for a state to be a single number, and it is why g has one index.

A contract is usable at frontier x when l <= x, and using it leaves the frontier at max(x, r + 1). Restricting to contracts with r >= x as well loses nothing, because a contract with r < x leaves the frontier where it was and only adds cost.

## Why the greedy cannot be repaired

Taking the furthest reach is optimal without costs because reaching further is never worse: any contract usable later after a shorter reach is also usable after a longer one. With costs, reaching further can cost more than it saves, and the comparison between "one expensive long contract" and "two cheap short ones" cannot be made without knowing what lies beyond, which is precisely what a table computes and a greedy refuses to.

## The boundary that breaks a careless implementation

The frontier after using [l, r] is r + 1, not r, because the positions are whole numbers and the contract covers position r itself. Using r leaves position r to be paid for twice and reports an answer that is too large, or loops forever when r == x.

Clamping to T + 1 matters when a contract reaches past T: without it the table needs indices beyond its length.

T = 0 is legal and means one position must be covered.

## Overflow

2000 contracts costing 10^6 reach 2 * 10^9. A signed 32 bit integer holds 2147483647, so even the worst possible total FITS, with about 147 million to spare. The INFINITY sentinel does not: setting it to the largest 32 bit value and then adding a cost wraps to a negative number, which the minimisation then happily accepts. Keep the table in 64 bit, or guard every addition.

## Related

Problem 1473 is this problem with every cost equal to 1, where the furthest-reach greedy is optimal and provable. Problem 462 is the same unweighted question over a half-open segment. Putting a cost on each contract is the smallest change that destroys the greedy, which is why the two sit next to each other.

Constraints - `0 ≤ T ≤ 2000` - `1 ≤ n ≤ 2000` - `0 ≤ l ≤ r ≤ 2000` - `1 ≤ c ≤ 1000000` - contracts cover the closed range of whole positions `[l, r]`, so two contracts ending at `p` and starting at `p + 1` leave nothing uncovered - contracts may overlap, repeat, and reach past `T`