LeetCode in Kotlin

4009. Minimum Possible Maximum Waiting Time

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:

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:

Solution

import 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
    }
}