Minimum Difficulty of a Job Schedule
Hard · Dynamic Programming · about 30 minutes
Asked at Amazon, Atlassian, Microsoft, Google, Salesforce, ServiceNow, Workday, Asana, Notion, GitLab, Airtable, Glean.
Jobs must be done in order; jobDifficulty[i] is job i's difficulty. Schedule them over d days, doing at least one job per day. A day's difficulty is the maximum difficulty of its jobs; the schedule's difficulty is the sum over days. Return the minimum schedule difficulty, or -1 if there are fewer jobs than days.