Skip to main content
Talentd

Minimum Possible Maximum Waiting Time - Solution & Explanation

HardArrayDynamic ProgrammingMemoization4 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given a list of task durations and a number of workers. Each worker handles one task at a time. You need to determine the minimum possible maximum waiting time for any task.

Approach 1: Brute Force (O(n * m))

Iterate through all possible waiting times and check if they can be achieved with the given number of workers. This involves simulating the task assignment process for each candidate waiting time. Use this approach to understand the problem constraints but avoid it in practice due to high complexity.

Approach 2: Binary Search (O(n log m))

Use binary search to find the minimum possible maximum waiting time. The key insight is that if a waiting time is achievable, any larger waiting time is also achievable. This allows you to narrow down the search space efficiently. Prefer this approach for its optimal balance between complexity and performance.

Recommended for interviews: Interviewers expect the binary search approach as it demonstrates efficient problem-solving skills. While the brute force method shows understanding, the optimal solution highlights your ability to optimize and apply advanced techniques.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n * m)O(1)When understanding problem constraints
Binary SearchO(n log m)O(1)General case, optimal solution

Video Solution

4009. Minimum Possible Maximum Waiting Time (Leetcode Hard) • Programming Live with Larry • 7 views views

Frequently Asked Questions

Is Minimum Possible Maximum Waiting Time easy or hard?
Minimum Possible Maximum Waiting Time is categorized as a hard problem due to its complexity and the need for an optimized approach like binary search.
Minimum Possible Maximum Waiting Time Python/Java solution
Solutions in Python and Java typically involve implementing binary search to find the minimum possible maximum waiting time efficiently.
How to solve Minimum Possible Maximum Waiting Time in O(n log m)?
Use binary search to determine the minimum possible maximum waiting time. This involves checking feasibility for each candidate waiting time and narrowing down the search space.
What is the best approach for Minimum Possible Maximum Waiting Time?
The best approach is binary search, which efficiently narrows down the minimum possible maximum waiting time with a complexity of O(n log m).
Is Minimum Possible Maximum Waiting Time asked at Google/Amazon/Meta?
Yes, Minimum Possible Maximum Waiting Time is a common problem asked in technical interviews at companies like Google, Amazon, and Meta.
What data structure is used in Minimum Possible Maximum Waiting Time?
Binary search is the primary technique used, leveraging the sorted nature of possible waiting times to achieve optimal performance.
What is the time complexity of Minimum Possible Maximum Waiting Time?
The optimal time complexity is O(n log m) using binary search, where n is the number of tasks and m is the range of possible waiting times.

Ready to solve this problem?

Practice Minimum Possible Maximum Waiting Time with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays