Cheapest Crew Assignment
HardBit Manipulation
Problem
A film production has n crew members and n shooting locations. cost[i][j] is the cost of sending crew member i to location j. Every crew member goes to exactly one location and every location gets exactly one crew member.
Return the minimum total cost.
Example 1
- Input:
- cost = [[4, 2, 8], [4, 3, 7], [3, 1, 6]]
- Output:
- 12
Crew 0 → location 1 (2), crew 1 → location 0 (4), crew 2 → location 2 (6).
Example 2
- Input:
- cost = [[1, 9], [9, 1]]
- Output:
- 2
Example 3
- Input:
- cost = [[5]]
- Output:
- 5
Constraints
- 1 ≤ n ≤ 15
- cost is n × n
- 0 ≤ cost[i][j] ≤ 10^4
Hint
Show the first hint
Greedy (each crew member takes their cheapest free location) fails. What information do you need to decide crew member i's location?
Walkthrough
How to approach it
01Clarify before coding
- Is the matrix always square? Yes, n crew and n locations.
- Can costs be 0? Yes, never negative.
- How large is n? Up to 15, so 2^15 · 15 states are fine but 15! permutations are not.
02Brute force
Try every permutation of locations and sum the costs.
Cost: O(n! · n): 15! ≈ 1.3 · 10^12 permutations. Impossible.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.