2449. Maximum Number Of Robots Within Budget¶

Difficulty: Hard

2449. Maximum Number of Robots Within Budget

Hard

You have n robots. You are given two 0-indexed integer arrays, chargeTimes and runningCosts, both of length n. The i^th 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 * 10⁴
1 <= chargeTimes[i], runningCosts[i] <= 10⁵
1 <= budget <= 10¹⁵

Solution¶

class Solution {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int n = chargeTimes.length;
        int low = 1, high = n, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (ok(mid, chargeTimes, runningCosts, budget)) {
                ans = mid;
                low = mid + 1;
            }
            else high = mid - 1;
        }
        return ans;
    }

    private boolean ok(int mid, int chargeTimes[], int runningCosts[], long budget) {
        int n = chargeTimes.length, start = 0;
        TreeSet<Integer> set = new TreeSet<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        long current_sum = 0;
        for (int i = 0; i < mid; i++) {
            int current = chargeTimes[i];
            set.add(current);
            map.put(current, map.getOrDefault(current, 0) + 1);
            current_sum += runningCosts[i];
        }
        long current_budget = set.last() * 1L +  mid * 1L * current_sum;
        if (current_budget <= budget) return true;
        for (int i = mid; i < n; i++) {
            int current = chargeTimes[i];
            current_sum += runningCosts[i]; current_sum -= runningCosts[start];
            map.put(current, map.getOrDefault(current, 0) + 1);
            map.put(chargeTimes[start], map.getOrDefault(chargeTimes[start], 0) -1);
            set.add(current);
            if (map.getOrDefault(chargeTimes[start], 0) == 0) {
                map.remove(chargeTimes[start]);
                set.remove(chargeTimes[start]);
            }
            start++;
            current_budget = set.last() * 1L + mid * (current_sum);
            if (current_budget <= budget) return true;
        }
        return false;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here