Minimum Difficulty of a Job Schedule
You are given a list of jobs that must be completed in their given order. The difficulty of job i is jobDifficulty.get(i).
Schedule all the jobs across exactly days days. At least one job must be completed each day. Because the jobs must be completed in order, the jobs assigned to each day form a contiguous group of the remaining jobs.
The difficulty of a day is the maximum difficulty among the jobs completed on that day. The total difficulty of a schedule is the sum of the difficulties of all days.
Return the minimum possible total difficulty. If it is impossible to schedule all jobs across exactly days days, return -1.
Method Signature
int minimumDifficulty(List<Integer> jobDifficulty, int days)
Parameters
jobDifficulty contains the difficulties of the jobs in the order in which they must be completed.days is the exact number of days available to complete all jobs.
Return Value
Return the minimum possible sum of daily difficulties. Return -1 if the number of jobs is smaller than days.
Constraints
1 <= jobDifficulty.size() <= 3000 <= jobDifficulty.get(i) <= 1,0001 <= days <= 10- Jobs must be completed in their original order.
- At least one job must be completed each day.
Examples
Example 1
minimumDifficulty(jobDifficulty = List.of(6, 5, 4, 3, 2, 1), days = 2)
Output: 7
Complete the first five jobs on the first day, whose difficulty is 6. Complete the final job on the second day, whose difficulty is 1. The total difficulty is 6 + 1 = 7.
Example 2
minimumDifficulty(jobDifficulty = List.of(9, 9, 9), days = 4)
Output: -1
There are fewer jobs than days, so it is impossible to complete at least one job every day.
Example 3
minimumDifficulty(jobDifficulty = List.of(1, 1, 1), days = 3)
Output: 3
Complete one job each day. Every day has difficulty 1, giving a total difficulty of 3.
Example 4
minimumDifficulty(jobDifficulty = List.of(7, 1, 7, 1, 7, 1), days = 3)
Output: 15
One optimal schedule has daily difficulties 7, 7, and 1. Their sum is 15.