1220. The Cheapest Way to Assign the Jobs

There are n workers and n jobs. A table gives the cost of each worker doing each job: row i is worker i and column j is job j. Give every worker exactly one job and every job exactly one worker, and report the smallest total cost.

costs 4 1 3 2 0 5 3 2 2 answer 5 worker 1 takes job 2, worker 2 takes job 1, worker 3 takes job 3 1 + 2 + 2 = 5

## What most people try first

Every assignment, all n! of them. At n = 9 that is 362880, which finishes, and it does the same work on an easy table as on a hard one, which is the thing worth fixing.

The greedy instinct is to give each worker their cheapest job in turn. It is wrong for the familiar reason: worker 1's cheapest job may be the only cheap job for worker 2. In the example above, greedy gives worker 1 job 2 at cost 1, then worker 2 is left with jobs 1 and 3 at costs 2 and 5 and takes job 1, then worker 3 takes job 3 at 2, total 5, which happens to be optimal. Change the first row to 4 1 1 and greedy still takes job 2 for worker 1, which now costs worker 2 its own cheapest job for no gain. Greedy here is a guess.

## The method, which is branch and bound

Assign the workers in order, trying each still-free job. The search is the easy part; the bound is the content.

The lower bound. Every worker not yet assigned will pay at least the cheapest cost in their own row, whatever job they end up with. So let rowmin[r] be the smallest entry in row r and tailmin[r] be the sum of rowmin[r], rowmin[r+1], .... At a node where workers 0 .. r-1 have been assigned at a total cost of acc, every completion costs at least acc + tailmin[r]. If that is already at or above the best total found so far, the branch cannot improve on it and is dead.

## What makes a bound sound

A bound is sound when every branch it skips contains no answer better than the one already found. That is the only thing that has to be proved, and it has to be proved rather than felt: a bound that is nearly sound gives a plausible wrong answer, which is the most expensive kind.

The shape of the argument is always the same. Find a quantity that moves in one direction as the search descends, then show that its value at the current node already rules the branch out. If the quantity can move both ways, the bound is not sound however reasonable it looks.

Here the quantity is acc + tailmin[r], and the direction is the one to check carefully: acc only grows as the search descends, and tailmin[r] shrinks by exactly rowmin[r] while acc grows by at least rowmin[r], since the cost paid by worker r is at least the smallest entry in its row. So the bound never decreases down a branch, which is what makes a single comparison at a node conclusive for everything below it.

The incumbent. The bound is only useful if there is something to compare against, so start with a real assignment rather than infinity. The identity, worker i takes job i, is always legal and its cost is a genuine upper bound, so use it. Starting from infinity makes the first descent do no pruning at all.

## Why the bound is admissible and not just plausible

rowmin[r] ignores which jobs are still free, so it can be optimistic: it may assume two workers both take the same cheap job. An optimistic estimate is exactly what a lower bound must be. A bound that accounted for the jobs already taken would be tighter and would cost more to compute, which is the usual trade; the loose one is enough here and it is obviously admissible, which matters more.

## The settled boundaries

A table where every entry is the same value w gives n * w whatever the assignment, which is a closed form the tests check. A table whose only zeros are on the diagonal gives 0, taken by the identity. n = 1 is a single cost.

## Cost

Worst case O(n!), which no bound removes, since the assignment problem has no polynomial algorithm of this shape. The Hungarian algorithm solves it in O(n^3) by a completely different route, and that is the right answer at large n; the point of this problem is the bound, which is the tool that applies when no such algorithm exists for your constraint.

Every cost is at most 1000 and n is at most 9, so the largest total is 9000, far below INT_MAX = 2147483647. A 32-bit integer is correct throughout.

Constraints - `1 ≤ n ≤ 9` - `0 ≤ each cost ≤ 1000` - the largest possible total is 9000, so a signed 32-bit integer is ample