Loading...
Loading...
Loading...
Meera runs the volunteer team for her college placement drive. She has n volunteers and n jobs, such as the registration desk, the water stall and guiding students to the halls.
The volunteers work at different speeds. Volunteer i needs cost[i][j] minutes to finish job j. Every volunteer must get exactly one job, and every job must go to exactly one volunteer.
Print the smallest possible total of minutes over all n jobs.
cost[i][0] to cost[i][n - 1] for volunteer i.long.Example 1
Input
3 9 2 7 6 4 3 5 8 1
Output
9
Volunteer 0 takes job 1 (2 minutes), volunteer 1 takes job 0 (6) and volunteer 2 takes job 2 (1). The total is 9.
Example 2
Input
1 5
Output
5
One volunteer and one job: the answer is 5.
Try the problem first. Open one hint at a time.
Hand out the jobs to the volunteers in order: volunteer 0 first, then volunteer 1, and so on. What matters at each step is only which jobs are already taken.
Store the set of taken jobs as the bits of an int called mask: bit j is 1 when job j is taken. There are 2^n such sets.
Let best[mask] be the smallest total for the taken jobs in mask. The next volunteer is the number of 1 bits in mask, and they can take any job whose bit is 0.
Start with best[0] = 0 and every other entry very large. Go through the masks in increasing order: adding a job only makes the mask bigger. The answer is best[2^n - 1].
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor