##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2398.html

# 2398. Maximum Number of Robots Within Budget

• Difficulty: Hard.
• Related Topics: Array, Binary Search, Queue, Sliding Window, Heap (Priority Queue), Prefix Sum.
• Similar Questions: Sliding Window Maximum, Kth Smallest Product of Two Sorted Arrays, Maximum Number of Tasks You Can Assign, Minimized Maximum of Products Distributed to Any Store, Minimum Time to Complete Trips.

## Problem

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.

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.


Constraints:

• chargeTimes.length == runningCosts.length == n

• 1 <= n <= 5 * 104

• 1 <= chargeTimes[i], runningCosts[i] <= 105

• 1 <= budget <= 1015

## Solution (Java, C++, Python)

• class Solution {
public int maximumRobots(int[] times, int[] costs, long budget) {
long sum = 0;
int i = 0, n = times.length;
for (int j = 0; j < n; ++j) {
sum += costs[j];
while (!d.isEmpty() && times[d.peekLast()] <= times[j])
d.pollLast();
if (times[d.getFirst()] + (j - i + 1) * sum > budget) {
if (d.getFirst() == i)
d.pollFirst();
sum -= costs[i++];
}
}
return n - i;
}
}

############

class Solution {
public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
Deque<Integer> q = new ArrayDeque<>();
int n = chargeTimes.length;
long s = 0;
int j = 0;
int ans = 0;
for (int i = 0; i < n; ++i) {
int a = chargeTimes[i], b = runningCosts[i];
while (!q.isEmpty() && chargeTimes[q.getLast()] <= a) {
q.pollLast();
}
q.offer(i);
s += b;
while (!q.isEmpty() && chargeTimes[q.getFirst()] + (i - j + 1) * s > budget) {
if (q.getFirst() == j) {
q.pollFirst();
}
s -= runningCosts[j++];
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}
}

• # 2398. Maximum Number of Robots Within Budget
# https://leetcode.com/problems/maximum-number-of-robots-within-budget/

from sortedcontainers import SortedList

class Solution:
def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
n = len(chargeTimes)
largest = SortedList()
res = i = costs = 0

for j in range(n):
costs += runningCosts[j]

total = -largest + (j - i + 1) * costs

while total > budget:
largest.remove(-chargeTimes[i])
costs -= runningCosts[i]
i += 1
total = -largest if largest else 0 + (j - i + 1) * costs

res = max(res, j - i + 1)

return res


• class Solution {
public:
int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
deque<int> q;
long long s = 0;
int ans = 0, j = 0, n = chargeTimes.size();
for (int i = 0; i < n; ++i) {
int a = chargeTimes[i], b = runningCosts[i];
while (!q.empty() && chargeTimes[q.back()] <= a) q.pop_back();
q.push_back(i);
s += b;
while (!q.empty() && chargeTimes[q.front()] + (i - j + 1) * s > budget) {
if (q.front() == j) {
q.pop_front();
}
s -= runningCosts[j++];
}
ans = max(ans, i - j + 1);
}
return ans;
}
};

• func maximumRobots(chargeTimes []int, runningCosts []int, budget int64) int {
s := int64(0)
ans, j := 0, 0
q := []int{}
for i, a := range chargeTimes {
for len(q) > 0 && chargeTimes[q[len(q)-1]] <= a {
q = q[:len(q)-1]
}
q = append(q, i)
s += int64(runningCosts[i])
for len(q) > 0 && int64(chargeTimes[q])+int64(i-j+1)*s > budget {
if q == j {
q = q[1:]
}
s -= int64(runningCosts[j])
j++
}
ans = max(ans, i-j+1)
}
return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).