Maximum Number of Robots Within Budget

hard sliding window monotonic deque queue

Problem

You have n robots with arrays chargeTimes and runningCosts. For k chosen robots the total cost is max(chargeTimes) + k · sum(runningCosts), where the max and sum are taken over those k robots. Return the maximum number of consecutive robots you can run so the total cost does not exceed budget.

InputchargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25

Output3

The first 3 robots cost max(3,6,1) + 3·sum(2,1,3) = 6 + 3·6 = 24 ≤ 25. No window of 4 fits, so the answer is 3.

chargeTimes (comma-separated)

runningCosts (comma-separated)

budget

def maximumRobots(chargeTimes, runningCosts, budget):
    n = len(chargeTimes)
    ans = run_sum = left = 0          # window answer, running-cost sum, left edge
    dq = deque()                      # indices, charge times decreasing
    for right in range(n):
        run_sum += runningCosts[right]           # extend window to the right
        while dq and chargeTimes[dq[-1]] <= chargeTimes[right]:
            dq.pop()                  # drop smaller charge times at the back
        dq.append(right)              # dq[0] is now the window maximum
        while dq and chargeTimes[dq[0]] + (right - left + 1) * run_sum > budget:
            if dq[0] == left:
                dq.popleft()          # the max is leaving the window
            run_sum -= runningCosts[left]        # shrink from the left
            left += 1
        ans = max(ans, right - left + 1)
    return ans

function maximumRobots(chargeTimes, runningCosts, budget) {
  const n = chargeTimes.length;
  let ans = 0, runSum = 0, left = 0;    // answer, running-cost sum, left edge
  const dq = [];                        // indices, charge times decreasing
  for (let right = 0; right < n; right++) {
    runSum += runningCosts[right];      // extend window to the right
    while (dq.length && chargeTimes[dq[dq.length - 1]] <= chargeTimes[right])
      dq.pop();                         // drop smaller charge times at the back
    dq.push(right);                     // dq[0] is now the window maximum
    while (dq.length && chargeTimes[dq[0]] + (right - left + 1) * runSum > budget) {
      if (dq[0] === left) dq.shift();   // the max is leaving the window
      runSum -= runningCosts[left];     // shrink from the left
      left++;
    }
    ans = Math.max(ans, right - left + 1);
  }
  return ans;
}

int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
    int n = chargeTimes.length, ans = 0, left = 0;
    long runSum = 0;                       // sum of running costs in window
    Deque<Integer> dq = new ArrayDeque<>(); // indices, charge times decreasing
    for (int right = 0; right < n; right++) {
        runSum += runningCosts[right];     // extend window to the right
        while (!dq.isEmpty() && chargeTimes[dq.peekLast()] <= chargeTimes[right])
            dq.pollLast();                 // drop smaller charge times at back
        dq.offerLast(right);               // dq.peekFirst() is the window max
        while (!dq.isEmpty() && chargeTimes[dq.peekFirst()] + (long)(right - left + 1) * runSum > budget) {
            if (dq.peekFirst() == left) dq.pollFirst(); // max leaving window
            runSum -= runningCosts[left];  // shrink from the left
            left++;
        }
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
}

int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
    int n = chargeTimes.size(), ans = 0, left = 0;
    long long runSum = 0;                  // sum of running costs in window
    deque<int> dq;                          // indices, charge times decreasing
    for (int right = 0; right < n; right++) {
        runSum += runningCosts[right];     // extend window to the right
        while (!dq.empty() && chargeTimes[dq.back()] <= chargeTimes[right])
            dq.pop_back();                 // drop smaller charge times at back
        dq.push_back(right);               // dq.front() is the window max
        while (!dq.empty() && chargeTimes[dq.front()] + (long long)(right - left + 1) * runSum > budget) {
            if (dq.front() == left) dq.pop_front(); // max leaving window
            runSum -= runningCosts[left];  // shrink from the left
            left++;
        }
        ans = max(ans, right - left + 1);
    }
    return ans;
}

Explanation

We want the longest contiguous block of robots whose cost max(charge) + size · sum(running) stays within budget. Because growing a window can only raise both the max and the sum, the cost is monotonic in window size for a fixed left edge — that makes a sliding window the natural tool.

We slide right across the array. Two quantities describe the current window: run_sum, the running-cost sum, kept by adding on the right and subtracting on the left; and the maximum charge time, which is trickier because elements both enter and leave.

To get the window maximum in amortized O(1) we keep a monotonic deque of indices whose charge times are non-increasing. When a new robot enters, we pop every index at the back with a charge time ≤ the newcomer's — they can never be the max again — then push the new index. The front of the deque, dq[0], is always the largest charge time in the window.

After extending, while the window's cost exceeds budget we shrink from the left: if the index leaving equals the deque's front, that maximum is leaving, so we pop the front too. Each index is pushed and popped at most once, so the whole scan is O(n).

After every step we record ans = max(ans, right - left + 1). For chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25, the widest fitting window is the first three robots, so the answer is 3.

Time: O(n) Space: O(n)