Minimum Difficulty of a Job Schedule

HardDynamic Programming2d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You must finish a list of jobs over exactly d days. The jobs have dependencies that force them to be done in the given order: to work on job i you must have finished every job before it. Each day you must complete at least one job. The difficulty of a day is the maximum jobDifficulty among the jobs done that day, and the difficulty of a schedule is the sum of its daily difficulties. Return the minimum possible schedule difficulty. If the jobs cannot be spread over d days (fewer jobs than days), return -1.

Examples

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Do jobs 0-4 on day 1 (max 6) and job 5 on day 2 (max 1), for 6 + 1 = 7.
Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Three jobs cannot fill four days.
Input: jobDifficulty = [1,1,1], d = 3
Output: 3
One job per day, each with difficulty 1.

Constraints

  • 1 <= jobDifficulty.length <= 300
  • 0 <= jobDifficulty[i] <= 1000
  • 1 <= d <= 10

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 2d dp problems