Hard
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. If both dispensers have enough fuel remaining, you may choose either of them, regardless of when they become free.demand[i], and the dispenser remains occupied for demand[i] seconds.demand[i] fuel remaining when car i becomes allowed, 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:
The following assignment serves all five cars:
| Car | Becomes allowed at | Starts refueling at | Dispenser used | Remaining fuel before start (dispenser 0, dispenser 1) |
Waiting time |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | (16, 13) | 0 |
| 1 | 0 | 0 | 1 | (10, 13) | 0 |
| 2 | 0 | 6 | 0 | (10, 5) | 6 |
| 3 | 6 | 10 | 0 | (6, 5) | 4 |
| 4 | 10 | 10 | 1 | (0, 5) | 0 |
Thus, all five cars are served, and the maximum waiting time is 6.
To serve all five cars, dispenser 0 must serve the cars with demands 6, 4, and 6, while dispenser 1 must serve the cars with demands 8 and 5. Therefore, car 2 must wait until time 6 for dispenser 0 to become free, so no assignment serving all five cars can have a maximum waiting time less than 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] <= 50import kotlin.math.max
class Solution {
fun minMaxWaitingTime(demand: IntArray, fuel: IntArray): Int {
val result = solve(0, fuel[0], fuel[1], 0, 0, demand, HashMap<Int?, Int?>())
return if ((result ushr 5) == 0) -1 else result and 31
}
private fun solve(
index: Int,
fuel0: Int,
fuel1: Int,
busy0: Int,
busy1: Int,
demand: IntArray,
memo: HashMap<Int?, Int?>,
): Int {
if (index == demand.size) {
return 0
}
val key = (index shl 22) or (fuel0 shl 16) or (fuel1 shl 10) or (busy0 shl 5) or busy1
val cached = memo[key]
if (cached != null) {
return cached
}
var best = 0
val required = demand[index]
if (fuel0 >= required) {
val wait = busy0
val child =
solve(
index + 1,
fuel0 - required,
fuel1,
required,
max(0, busy1 - wait),
demand,
memo,
)
best = (1 + (child ushr 5)) * 32 + max(wait, child and 31)
}
if (fuel1 >= required) {
val wait = busy1
val child =
solve(
index + 1,
fuel0,
fuel1 - required,
max(0, busy0 - wait),
required,
demand,
memo,
)
val candidate = (1 + (child ushr 5)) * 32 + max(wait, child and 31)
if ((candidate ushr 5) > (best ushr 5) ||
((candidate ushr 5) == (best ushr 5) && (candidate and 31) < (best and 31))
) {
best = candidate
}
}
memo[key] = best
return best
}
}