Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Problem list
DescriptionHints 4Video 1:11:36

4009. Minimum Possible Maximum Waiting Time

Hard29.9% acceptance

You are given an integer array demand, where demand[i] is the amount of fuel required by the ith car.

You are also given an integer array fuel of length 2. There are exactly two fuel dispensers, numbered 0 and 1, where fuel[j] is the initial amount of fuel available in dispenser j.

Cars are allowed to start refueling in increasing index order. Car 0 becomes allowed at time 0, and for each i > 0, car i becomes allowed exactly when car i - 1 starts refueling.

The refueling process follows these rules:

  • Each dispenser can serve at most one car at a time.
  • A car may start refueling at any time at or after it becomes allowed.
  • A car can start on a dispenser only if the dispenser is free and has at least demand[i] fuel remaining.
  • If multiple free dispensers can serve the current car, you may choose any of them.
  • Refueling a car takes demand[i] seconds and reduces the remaining fuel in that dispenser by demand[i].
  • Once started, refueling cannot be interrupted.
  • When both dispensers are free, if neither has at least demand[i] fuel remaining, the process terminates and no further cars can be served.

The waiting time of a car is the time between when it becomes allowed to start refueling and when it actually starts.

Return the minimum possible value of the maximum waiting time among all served cars over all assignments that maximize the number of served cars. If no car can be served, return -1.

Example 1:

Input: demand = [6,8,4,6,5], fuel = [16,13]

Output: 6

Explanation:

Car Becomes allowed at Starts refueling at Dispenser used Remaining fuel before start
(dispenser 0, dispenser 1)		 Waiting time
0 0 0 1 (16, 13) 0
1 0 0 0 (16, 7) 0
2 0 6 1 (8, 7) 6
3 6 8 0 (8, 3) 2

Car 4 becomes allowed at time 8, but when both dispensers are free, their remaining fuel is (2, 3), which is less than demand[4] = 5.

Therefore, the process terminates. The maximum waiting time among served cars is 6.

Example 2:

Input: demand = [10,15], fuel = [12,17]

Output: 0

Explanation:

  • At time 0, Car 0 becomes allowed and starts refuelling using dispenser 0.
  • Car 1 becomes allowed at time 0 (when Car 0 starts) and immediately starts refuelling using dispenser 1.
  • Both cars start without waiting, so the maximum waiting time is 0.

Example 3:

Input: demand = [10,5], fuel = [8,8]

Output: -1

Explanation:

  • At time 0, Car 0 becomes allowed. However, neither dispenser has enough fuel to serve it, so the process terminates immediately.
  • No car is served, so the answer is -1.

Constraints:

  • 1 <= demand.length <= 50
  • 1 <= demand[i] <= 20
  • fuel.length == 2
  • 1 <= fuel[i] <= 50

Topics

ArrayDynamic ProgrammingMemoization

Hints open one at a time

Hint 1

Use dynamic programming over the cars in order. For each dispenser, store its remaining fuel and the time until it becomes free, measured from when the current car becomes allowed.

Hint 2

If the current car is assigned to a dispenser whose remaining busy time is wait, its waiting time is wait. Decrease that dispenser's fuel and set its new busy time to demand[i].

Hint 3

Because the next car becomes allowed when the current car starts, subtract wait from the other dispenser's busy time, stopping at 0.

Hint 4

For every state, first maximize the number of cars that can be served. Among assignments serving that maximum number, minimize the maximum waiting time encountered.

Loading editor…
1class Solution:
2 def minMaxWaitingTime(self, demand: List[int], fuel: List[int]) -> int:
3
Starter codePython 3Spaces: 4
Examples
Input
[6,8,4,6,5]
[16,13]
Input
[10,15]
[12,17]
Input
[10,5]
[8,8]
Your code is saved on this device.