Schedule a Job Pipeline Over D Days
A pipeline has ordered jobs, each with a difficulty. You must finish it in exactly D days, doing at least one job per day and keeping jobs in order. A day's difficulty is its hardest job; total difficulty is the sum across days. Minimize it.
Problem
Given jobDifficulty[i] (jobs must be done in order) and an integer d, schedule all jobs over exactly d days with at least one job per day. The difficulty of a day equals the maximum jobDifficulty among that day's jobs. Return the minimum total difficulty, or -1 if impossible (n < d).
Input
An integer array jobDifficulty of length n in [1, 300] and an integer d in [1, 10]. Values in [0, 1000].
Output
An integer: minimum total scheduling difficulty, or -1.
Constraints
- 1 <= jobDifficulty.length <= 300
- 0 <= jobDifficulty[i] <= 1000
- 1 <= d <= 10
Examples
Example 1
Input
jobDifficulty = [6,5,4,3,2,1], d = 2
Output
7
Day 1: [6,5,4,3,2] (max 6), Day 2: [1] (max 1) → 7.
Example 2
Input
jobDifficulty = [9,9,9], d = 4
Output
-1
Only 3 jobs cannot fill 4 days.