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

  • 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
    }
    
  • function maximumRobots(chargeTimes: number[], runningCosts: number[], budget: number): number {
        const q = new Deque<number>();
        const n = chargeTimes.length;
        let [ans, s] = [0, 0];
        for (let l = 0, r = 0; r < n; ++r) {
            s += runningCosts[r];
            while (!q.isEmpty() && chargeTimes[q.backValue()!] <= chargeTimes[r]) {
                q.popBack();
            }
            q.pushBack(r);
            while (!q.isEmpty() && (r - l + 1) * s + chargeTimes[q.frontValue()!] > budget) {
                if (q.frontValue() === l) {
                    q.popFront();
                }
                s -= runningCosts[l++];
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
    
    class Node<T> {
        value: T;
        next: Node<T> | null;
        prev: Node<T> | null;
    
        constructor(value: T) {
            this.value = value;
            this.next = null;
            this.prev = null;
        }
    }
    
    class Deque<T> {
        private front: Node<T> | null;
        private back: Node<T> | null;
        private size: number;
    
        constructor() {
            this.front = null;
            this.back = null;
            this.size = 0;
        }
    
        pushFront(val: T): void {
            const newNode = new Node(val);
            if (this.isEmpty()) {
                this.front = newNode;
                this.back = newNode;
            } else {
                newNode.next = this.front;
                this.front!.prev = newNode;
                this.front = newNode;
            }
            this.size++;
        }
    
        pushBack(val: T): void {
            const newNode = new Node(val);
            if (this.isEmpty()) {
                this.front = newNode;
                this.back = newNode;
            } else {
                newNode.prev = this.back;
                this.back!.next = newNode;
                this.back = newNode;
            }
            this.size++;
        }
    
        popFront(): T | undefined {
            if (this.isEmpty()) {
                return undefined;
            }
            const value = this.front!.value;
            this.front = this.front!.next;
            if (this.front !== null) {
                this.front.prev = null;
            } else {
                this.back = null;
            }
            this.size--;
            return value;
        }
    
        popBack(): T | undefined {
            if (this.isEmpty()) {
                return undefined;
            }
            const value = this.back!.value;
            this.back = this.back!.prev;
            if (this.back !== null) {
                this.back.next = null;
            } else {
                this.front = null;
            }
            this.size--;
            return value;
        }
    
        frontValue(): T | undefined {
            return this.front?.value;
        }
    
        backValue(): T | undefined {
            return this.back?.value;
        }
    
        getSize(): number {
            return this.size;
        }
    
        isEmpty(): boolean {
            return this.size === 0;
        }
    }
    
    

All Problems

All Solutions