Garden Crew Assignment
Medium · bit manipulation
A town garden has n flowerbeds that all need planting today, and a crew of n gardeners. Each gardener plants exactly one bed, and each bed is planted by exactly one gardener.
You are given a grid minutes with n rows and n columns. The entry minutes[i][j] is the number of minutes that gardener i needs to plant bed j. The gardeners work at the same time, but the council pays for every minute worked, so what matters is the total of all the minutes.
Return the smallest possible total number of minutes over all the ways to hand the beds out.
Examples
Example 1
Input: minutes = [[3, 5], [4, 2]]
Output: 5
Gardener 0 plants bed 0 (3 minutes) and gardener 1 plants bed 1 (2 minutes). The other way round costs 5 + 4 = 9.
Example 2
Input: minutes = [[4, 2, 8], [2, 3, 7], [3, 1, 6]]
Output: 10
Gardener 0 takes bed 1 (2), gardener 1 takes bed 0 (2) and gardener 2 takes bed 2 (6), which makes 10.
Example 3
Input: minutes = [[9]]
Output: 9
One gardener, one bed.
Constraints
- 1 <= n <= 10, where n is the number of rows and columns of minutes
- 1 <= minutes[i][j] <= 1000