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)

• Java
• Python
• C++
• Go

• class Solution {
      public int maximumRobots(int[] times, int[] costs, long budget) {
          long sum = 0;
          int i = 0, n = times.length;
          Deque<Integer> d = new LinkedList<Integer>();
          for (int j = 0; j < n; ++j) {
              sum += costs[j];
              while (!d.isEmpty() && times[d.peekLast()] <= times[j])
                  d.pollLast();
              d.addLast(j);
              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):
              largest.add(-chargeTimes[j])
              costs += runningCosts[j]
              
              total = -largest[0] + (j - i + 1) * costs
              
              while total > budget:
                  largest.remove(-chargeTimes[i])
                  costs -= runningCosts[i]
                  i += 1
                  total = -largest[0] 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[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
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

Explain:

nope.

Complexity:

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

All Problems

All Solutions