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:
demand[i] fuel remaining.demand[i] seconds and reduces the remaining fuel in that dispenser by demand[i].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:
Example 3:
Input: demand = [10,5], fuel = [8,8]
Output: -1
Explanation:
Constraints:
1 <= demand.length <= 501 <= demand[i] <= 20fuel.length == 21 <= fuel[i] <= 50Problem 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| 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 |
Practice Minimum Possible Maximum Waiting Time with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor