FastPrep
Problem · Array

Minimum Effort Task Schedule

Learn this problem
● HardMicrosoftNEW GRADOA
See Microsoft hiring insights

Problem statement

A project manager is assigning a series of tasks for the team. There is a list of n tasks that need to be completed in order, and each requires a level of effort. All the tasks need to be completed within deadline days.

The manager wants to plan the tasks such that there is at least one task on each day and the sum of the levels of effort of all the days is minimum. The level of effort of a day is given by the highest level of effort of any task that is performed on that day. Find this minimum sum of effort.

Complete the function minimumEffort.

minimumEffort has the following parameters:

  • int efforts[n]: the order and effort required for the tasks.
  • int deadline: the number of days in which all of the tasks must be completed.

Return the minimum overall level of effort that can be achieved with optimal planning.

Function

minimumEffort(efforts: int[], deadline: int) → int

Examples

Example 1

efforts = [1, 2, 3, 4, 5]deadline = 3return = 8

An optimal plan is:

  • Day 1: the first task, with effort 1.
  • Day 2: the second task, with effort 2.
  • Day 3: the remaining tasks, with effort max(3, 4, 5) = 5.

The sum of the levels of effort of all the days is 1 + 2 + 5 = 8. Return 8.

Constraints

  • 1 <= n <= 300
  • 1 <= deadline <= n <= 300

More Microsoft problems

drafts saved locally
public int minimumEffort(int[] efforts, int deadline) {
    // write your code here
}
efforts[1, 2, 3, 4, 5]
deadline3
expected8
checking account