Minimum Possible Maximum Waiting Time - Video Solutions
4009. Minimum Possible Maximum Waiting Time (Leetcode Hard)
Minimum Possible Maximum Waiting Time - Video Solution
Watch the video solution for Minimum Possible Maximum Waiting Time, a hard level problem involving Array, Dynamic Programming, Memoization. This walkthrough by Programming Live with Larry has 7 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 bydemand[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 <= 501 <= demand[i] <= 20fuel.length == 21 <= 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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n * m) | O(1) | When understanding problem constraints |
| Binary Search | O(n log m) | O(1) | General case, optimal solution |