The number of set bits says whose turn it is
When you hand items out one person at a time, the count of used items tells you who is next. About 15 minutes.
One job for each worker
You have n workers and n jobs. Worker i does job j at a cost that you are given in a table. Every worker gets exactly one job and every job goes to exactly one worker. What is the smallest total cost?
Trying every way to pair them up is n factorial possibilities. But think of handing out jobs worker by worker: the only thing that matters for what is left to do is which jobs are already taken.
Count the taken jobs to find the worker
Serve the workers in order: worker 0, then worker 1, and so on. After some jobs are taken, how many workers have been served? Exactly as many as there are jobs taken. So the number of switched-on bits in the set is also the number of the next worker.
For every set of taken jobs, keep the smallest total cost so far. Give the next worker each free job in turn, add the cost, and update the bigger set. The answer is the cost for the set with every job taken.
worker = bin(mask).count("1")
# jobs taken so farNo jobs taken: cost 0. Worker 0 is next. Costs: worker 0 pays A 9, B 2, C 7. Worker 1 pays A 6, B 4, C 3. Worker 2 pays A 5, B 8, C 1.
Two jobs are taken. Which worker gets to choose the next job?
- AThe third worker, worker 2
- BThe second worker, worker 1
- CAny worker, it depends on which jobs are taken
Show the answer
The third worker, worker 2. Workers 0 and 1 have been served, one per taken job, so worker 2 is next.
Assign jobs to workers
There are n workers and n jobs. cost[i][j] is the cost of worker i doing job j. Give each worker exactly one job so that every job is done by exactly one worker, and return the smallest possible total cost.
cost = [[9, 2, 7], [6, 4, 3], [5, 8, 1]] → 9
1 ≤ n ≤ 14 · 1 ≤ cost[i][j] ≤ 1,000