LeetCode 2398: Maximum Number of Robots Within Budget Solution

Master LeetCode problem 2398 (Maximum Number of Robots Within Budget), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2398. Maximum Number of Robots Within Budget

Hard

Array Binary Search Queue Sliding Window Heap (Priority Queue)Prefix Sum Monotonic Queue

Problem Explanation

Explanation:

To solve this problem, we can use a sliding window approach. We will maintain a window of consecutive robots and keep track of the total charge cost and total running cost within the window. We will iterate through the robots and continuously expand the window until the total cost exceeds the budget. At each step, we will update the maximum number of consecutive robots that can be run within the budget.

Sort the robots based on their charge times.
Initialize variables to track current window's charge cost, running cost, maximum number of robots, and the current number of robots.
Iterate through the robots, updating the window's cost and number of robots.
If the total cost exceeds the budget, shrink the window from the left side and update the current window's cost and number of robots.
Keep track of the maximum number of robots that can be run within the budget.
Return the maximum number of robots.

Time Complexity: O(n log n) where n is the number of robots (for sorting) Space Complexity: O(1)

Solution Code

import java.util.Arrays;

class Solution {
    public int maxNumberOfRobots(int[] chargeTimes, int[] runningCosts, int budget) {
        int n = chargeTimes.length;
        int[][] robots = new int[n][2];
        for (int i = 0; i < n; i++) {
            robots[i] = new int[]{chargeTimes[i], runningCosts[i]};
        }
        Arrays.sort(robots, (a, b) -> a[0] - b[0]);

        int maxRobots = 0;
        long totalCharge = 0, totalRunning = 0;
        int left = 0;

        for (int right = 0; right < n; right++) {
            totalCharge += robots[right][0];
            totalRunning += robots[right][1];
            
            while (totalCharge + (long)totalRunning * (right - left) > budget) {
                totalCharge -= robots[left][0];
                totalRunning -= robots[left][1];
                left++;
            }

            maxRobots = Math.max(maxRobots, right - left + 1);
        }

        return maxRobots;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2398 (Maximum Number of Robots Within Budget)?

This page provides optimized solutions for LeetCode problem 2398 (Maximum Number of Robots Within Budget) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2398 (Maximum Number of Robots Within Budget)?

The time complexity for LeetCode 2398 (Maximum Number of Robots Within Budget) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2398 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2398 in Java, C++, or Python.

Back to LeetCode Solutions