Maximum Number of Robots Within Budget
01 · Problem
There are n robots in a row. Robot i has a charge time chargeTimes[i] and a running cost runningCosts[i]. You also have an integer budget.
If you run a group of k robots, the total cost is
max(chargeTimes of the group) + k * sum(runningCosts of the group).
You may only run a contiguous block of robots. Return the largest k such that some block of k consecutive robots has total cost at most budget. If not even one robot fits, return 0.
02 · Examples
chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
3
Running the first three robots costs max(3,6,1) + 3 * (2+1+3) = 6 + 18 = 24, which fits in 25. Every window of four robots costs more than 25.
chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
0
Even a single robot costs at least 11 + 1 * 10 = 21, which exceeds 19, so no robots can run.
chargeTimes = [1,1,1,1], runningCosts = [1,1,1,1], budget = 17
4
All four robots cost 1 + 4 * 4 = 17, exactly the budget.
03 · Constraints
- 01chargeTimes.length == runningCosts.length == n
- 021 <= n <= 5 * 104
- 031 <= chargeTimes[i], runningCosts[i] <= 105
- 041 <= budget <= 1015
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.