FastPrep
Problem · Array

Minimize Maximum Pilot Workload

Learn this problem
● MediumSpotnanaFULLTIMEONSITE INTERVIEW

Problem statement

You are given an integer array flights, where flights[i] is the duration of the i-th flight, and an integer k representing the number of available pilots.

Assign every flight to exactly one pilot while preserving the original flight order. Each pilot must receive one non-empty contiguous sequence of flights. A pilot's workload is the sum of the durations assigned to that pilot.

Return the minimum possible value of the maximum workload among all k pilots.

Function

minimizeMaximumPilotTime(flights: int[], k: int) → long

Examples

Example 1

flights = [10,20,30,40]k = 2return = 60

Assign [10,20,30] to one pilot and [40] to the other. Their workloads are 60 and 40. No partition can make the larger workload less than 60.

Example 2

flights = [5,1,2,7,3,4]k = 3return = 8

The groups [5,1,2], [7], and [3,4] have workloads 8, 7, and 7.

Constraints

  • 1 <= k <= flights.length <= 100000
  • 1 <= flights[i] <= 1000000000
  • The answer fits in a signed 64-bit integer.

More Spotnana problems

drafts saved locally
public long minimizeMaximumPilotTime(int[] flights, int k) {
  // write your code here
}
flights[10,20,30,40]
k2
expected60
checking account