Welcome to Subscribe On Youtube

2398. Maximum Number of Robots Within Budget

Description

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

Solutions

• Java
• C++
• Python
• Go

• 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;
      }
  }
  

• 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;
      }
  };
  

• class Solution:
      def maximumRobots(
          self, chargeTimes: List[int], runningCosts: List[int], budget: int
      ) -> int:
          q = deque()
          ans = j = s = 0
          for i, (a, b) in enumerate(zip(chargeTimes, runningCosts)):
              while q and chargeTimes[q[-1]] <= a:
                  q.pop()
              q.append(i)
              s += b
              while q and chargeTimes[q[0]] + (i - j + 1) * s > budget:
                  if q[0] == j:
                      q.popleft()
                  s -= runningCosts[j]
                  j += 1
              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[0]])+int64(i-j+1)*s > budget {
  			if q[0] == j {
  				q = q[1:]
  			}
  			s -= int64(runningCosts[j])
  			j++
  		}
  		ans = max(ans, i-j+1)
  	}
  	return ans
  }
  

All Problems

All Solutions