Maximum number of robots within budget

Array Binary Search Queue Sliding Window Heap (Priority Queue) Prefix Sum Monotonic Queue

38.1% acceptance

Feb 25, 2026

908

You have n robots. You are given two 0-indexed integer arrays, chargeTimes and runningCosts, both of length n. The ith robot costs chargeTimes[i] units to charge and costs runningCosts[i] units to run. You are also given an integer budget. The total cost of running k chosen robots is equal to max(chargeTimes) + k * sum(runningCosts), where max(chargeTimes) is the largest charge cost among the k robots and sum(runningCosts) is the sum of running costs among the k robots. Return the maximum number of consecutive robots you can run such that the total cost does not exceed budget.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_robots(charge_times: Vec<i32>, running_costs: Vec<i32>, budget: i64) -> i32 {
    use std::collections::VecDeque;
    let n = charge_times.len();
    let mut deq: VecDeque<usize> = VecDeque::new();
    let mut run_sum: i64 = 0;
    let mut l = 0usize;
    let mut ans = 0;
    for r in 0..n {
      while deq.back().map(|&i| charge_times[i] <= charge_times[r]).unwrap_or(false) {
        deq.pop_back();
      }
      deq.push_back(r);
      run_sum += running_costs[r] as i64;
      while l <= r {
        let k = (r - l + 1) as i64;
        let max_ct = charge_times[*deq.front().unwrap()] as i64;
        if max_ct + k * run_sum <= budget { break; }
        if deq.front() == Some(&l) { deq.pop_front(); }
        run_sum -= running_costs[l] as i64;
        l += 1;
      }
      ans = ans.max((r + 1).saturating_sub(l));
    }
    ans as i32
  }
}