Maximum Number of Robots Within Budget
You have n robots. You are given two 0-indexed integer arrays, chargeTimes and runningCosts, both of length n. The i^th 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.
Example 1
Input
chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25Output
3The first 3 robots have total cost
max(3,6,1) + 3 * sum(2,1,3) = 24, and no longer consecutive group fits within the budget.Example 2
Input
chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19Output
0No robot can be run without exceeding the budget, so the maximum number is 0.
Constraints
- chargeTimes.length == runningCosts.length == n
- 1 <= n <= 5 * 10^4
- 1 <= chargeTimes[i], runningCosts[i] <= 10^5
- 1 <= budget <= 10^15
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.