#2398

Maximum Number of Robots Within Budget

master · 1755 · lc hard +32 · verified · 38.1% accepted · 909 likes · top 17%

⚑ Monotonic Deque (Sliding Window Max/Min)

Description

You have n robots. You are given two 0-indexed integer arrays chargeTimes and runningCosts, both of length n. You also have a budget integer budget.

The cost of running a contiguous group of robots from index i to j (inclusive) for one unit of time is max(chargeTimes[i..j]) + (j - i + 1) * sum(runningCosts[i..j]).

Return the maximum number of consecutive robots you can run within the budget.

Example 1:

Input: chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25

Output: 3

Explanation:

It is possible to run all individual and consecutive pairs of robots within budget.

To obtain answer 3, consider the first 3 robots. The total cost will be max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 which is less than 25.

It can be shown that it is not possible to run more than 3 consecutive robots within budget, so we return 3.

Example 2:

Input: chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19

Output: 0

Explanation: No robot can be run that does not exceed the budget, so we return 0.

Code

1

2

3

class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:

class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int: