Skip to content

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

Solution 1: Two Pointers + Monotonic Queue

The problem is essentially finding the maximum value within a sliding window, which can be solved using a monotonic queue.

We only need to use binary search to enumerate the size of the window \(k\), and find the largest \(k\) that satisfies the problem requirements.

In the implementation process, we don't actually need to perform binary search enumeration. We just need to change the fixed window to a non-fixed window with double pointers.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the number of robots in the problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maximumRobots(
        self, chargeTimes: List[int], runningCosts: List[int], budget: int
    ) -> int:
        q = deque()
        ans = s = l = 0
        for r, (t, c) in enumerate(zip(chargeTimes, runningCosts)):
            s += c
            while q and chargeTimes[q[-1]] <= t:
                q.pop()
            q.append(r)
            while q and (r - l + 1) * s + chargeTimes[q[0]] > budget:
                if q[0] == l:
                    q.popleft()
                s -= runningCosts[l]
                l += 1
            ans = max(ans, r - l + 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        Deque<Integer> q = new ArrayDeque<>();
        int n = chargeTimes.length;
        int ans = 0;
        long s = 0;
        for (int l = 0, r = 0; r < n; ++r) {
            s += runningCosts[r];
            while (!q.isEmpty() && chargeTimes[q.peekLast()] <= chargeTimes[r]) {
                q.pollLast();
            }
            q.offerLast(r);
            while (!q.isEmpty() && (r - l + 1) * s + chargeTimes[q.peekFirst()] > budget) {
                if (q.peekFirst() == l) {
                    q.pollFirst();
                }
                s -= runningCosts[l++];
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        deque<int> q;
        long long s = 0;
        int ans = 0;
        int n = chargeTimes.size();
        for (int l = 0, r = 0; r < n; ++r) {
            s += runningCosts[r];
            while (q.size() && chargeTimes[q.back()] <= chargeTimes[r]) {
                q.pop_back();
            }
            q.push_back(r);
            while (q.size() && (r - l + 1) * s + chargeTimes[q.front()] > budget) {
                if (q.front() == l) {
                    q.pop_front();
                }
                s -= runningCosts[l++];
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
func maximumRobots(chargeTimes []int, runningCosts []int, budget int64) (ans int) {
    q := Deque{}
    s := int64(0)
    l := 0
    for r, t := range chargeTimes {
        s += int64(runningCosts[r])
        for !q.Empty() && chargeTimes[q.Back()] <= t {
            q.PopBack()
        }
        q.PushBack(r)
        for !q.Empty() && int64(r-l+1)*s+int64(chargeTimes[q.Front()]) > budget {
            if q.Front() == l {
                q.PopFront()
            }
            s -= int64(runningCosts[l])
            l++
        }
        ans = max(ans, r-l+1)
    }
    return
}

// template
type Deque struct{ l, r []int }

func (q Deque) Empty() bool {
    return len(q.l) == 0 && len(q.r) == 0
}

func (q Deque) Size() int {
    return len(q.l) + len(q.r)
}

func (q *Deque) PushFront(v int) {
    q.l = append(q.l, v)
}

func (q *Deque) PushBack(v int) {
    q.r = append(q.r, v)
}

func (q *Deque) PopFront() (v int) {
    if len(q.l) > 0 {
        q.l, v = q.l[:len(q.l)-1], q.l[len(q.l)-1]
    } else {
        v, q.r = q.r[0], q.r[1:]
    }
    return
}

func (q *Deque) PopBack() (v int) {
    if len(q.r) > 0 {
        q.r, v = q.r[:len(q.r)-1], q.r[len(q.r)-1]
    } else {
        v, q.l = q.l[0], q.l[1:]
    }
    return
}

func (q Deque) Front() int {
    if len(q.l) > 0 {
        return q.l[len(q.l)-1]
    }
    return q.r[0]
}

func (q Deque) Back() int {
    if len(q.r) > 0 {
        return q.r[len(q.r)-1]
    }
    return q.l[0]
}

func (q Deque) Get(i int) int {
    if i < len(q.l) {
        return q.l[len(q.l)-1-i]
    }
    return q.r[i-len(q.l)]
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
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;
    }
}

Comments