We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Robots Within Budget

Number: 2449

Difficulty: Hard

Paid? No

Companies: InMobi, Amazon

Problem Description

Given two arrays, chargeTimes and runningCosts, representing the charging cost and running cost for each robot respectively, and an integer budget, determine the maximum number of consecutive robots that can be operated without exceeding the budget. The total cost for a group of robots is defined as the maximum charge time of the group plus the group size multiplied by the sum of their running costs.

Key Insights

  • Use a sliding window to consider consecutive robots.
  • Maintain the sum of runningCosts in the current window.
  • Use a monotonic deque (max queue) to keep track of the maximum chargeTime in the current window efficiently.
  • Expand the window by moving the right pointer and, when the cost exceeds the budget, shrink the window by moving the left pointer.
  • The cost formula is: currentMaxCharge + windowSize * currentSumRunningCosts <= budget.

Space and Time Complexity

Time Complexity: O(n) – Each element is processed at most twice (once when added and once when removed from the window/deque). Space Complexity: O(n) – In the worst case, the deque can store all indices.

Solution

The solution uses a sliding window approach along with a monotonic deque to efficiently determine the maximum charge time in the current window. For each new index added:

  1. Add the new robot's running cost to the running sum.
  2. Remove elements from the deque’s back if they are less than the current robot's charge time; this maintains a decreasing order.
  3. Append the current index to the deque.
  4. While the total cost (max charge from deque’s front + window length * running sum) exceeds the budget, move the left pointer of the window to shrink it. If the left pointer equals the index at the front of the deque, pop it from the deque.
  5. Throughout the process, track the maximum window length that satisfies the cost condition.

Code Solutions

# Python solution for Maximum Number of Robots Within Budget

from collections import deque

def maximumRobots(chargeTimes, runningCosts, budget):
    n = len(chargeTimes)
    max_len = 0
    totalRunningCost = 0
    maxDeque = deque()  # stores indices of chargeTimes in decreasing order
    left = 0

    for right in range(n):
        # Add running cost for the new robot
        totalRunningCost += runningCosts[right]
        
        # Maintain the monotonic deque for chargeTimes
        while maxDeque and chargeTimes[maxDeque[-1]] <= chargeTimes[right]:
            maxDeque.pop()
        maxDeque.append(right)
        
        # Calculate the current cost
        currentWindowSize = right - left + 1
        # Maximum chargeTime is at the front of the deque
        currentCost = chargeTimes[maxDeque[0]] + currentWindowSize * totalRunningCost
        
        # Shrink window from left if cost exceeds budget
        while currentCost > budget and left <= right:
            # Remove the left element's running cost from total
            totalRunningCost -= runningCosts[left]
            # If the removed element is the maximum, pop it from deque
            if maxDeque and maxDeque[0] == left:
                maxDeque.popleft()
            left += 1
            
            currentWindowSize = right - left + 1
            if currentWindowSize > 0:
                currentCost = chargeTimes[maxDeque[0]] + currentWindowSize * totalRunningCost
            else:
                currentCost = 0
        
        # Update maximum valid window length
        max_len = max(max_len, right - left + 1)
    
    return max_len

# Example usage:
chargeTimes = [3,6,1,3,4]
runningCosts = [2,1,3,4,5]
budget = 25
print(maximumRobots(chargeTimes, runningCosts, budget))  # Expected output: 3
← Back to All Questions