Find maximum waiting time.


  • 1
    P

    There are 3 fueling pumps(1, 2, ,3) with fixed capacity. There is a queue of vehicles waiting for fuel. It takes 1 second to fuel 1 gallon. If multiple pumps can satisfy the vehicle, then the pump with least index takes preference. Compute the maximum wait time?


  • 2
    E

    Let me attempt to formalize the problem and then present a solution.
    There is a queue with n cars, represented by an array i, and car i needs to fuel a[i] gallons. There are k pumps that can serve the cars. It takes 1 second to fuel 1 gallon. The time it takes for the car in the front of the queue to get to an available pump is negligible. Find out how long the last car has to wait.

    Solution: Keep track of the current time in seconds by variable t. Two things can happen in each step:

    1. Car i is in front of the queue, and it enters an available pump. In this case we know that this pump will be available again at time t + a[i]. We push this number into a priority queue. If i is equal to n-1, just return t.
    2. All the pumps are busy. In this case, we pop the earliest time p in which a pump becomes available, and update t = p.
    int maxWaitTime(const vector<int> &a, int k) {
        int t = 0, i = 0, n = a.size();
        priority_queue<int, vector<int>, greater<int>> q;
        while (i < n) {
            if (q.size() < k) {
                if (i == n-1) return t;
                q.push(a[i++] + t);
            }
            else {
                t = q.top();
                q.pop();
            }
        }
        return -1;
    }
    

  • 0
    R

    @elastico The code looks good for unlimited amount of fuel in each pump. However, it says each pump has some limited amount of fuel.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.