Skip to content

3814. Maximum Capacity Within Budget

Description

You are given two integer arrays costs and capacity, both of length n, where costs[i] represents the purchase cost of the ith machine and capacity[i] represents its performance capacity.

You are also given an integer budget.

You may select at most two distinct machines such that the total cost of the selected machines is strictly less than budget.

Return the maximum achievable total capacity of the selected machines.

Β 

Example 1:

Input: costs = [4,8,5,3], capacity = [1,5,2,7], budget = 8

Output: 8

Explanation:

  • Choose two machines with costs[0] = 4 and costs[3] = 3.
  • The total cost is 4 + 3 = 7, which is strictly less than budget = 8.
  • The maximum total capacity is capacity[0] + capacity[3] = 1 + 7 = 8.

Example 2:

Input: costs = [3,5,7,4], capacity = [2,4,3,6], budget = 7

Output: 6

Explanation:

  • Choose one machine with costs[3] = 4.
  • The total cost is 4, which is strictly less than budget = 7.
  • The maximum total capacity is capacity[3] = 6.

Example 3:

Input: costs = [2,2,2], capacity = [3,5,4], budget = 5

Output: 9

Explanation:

  • Choose two machines with costs[1] = 2 and costs[2] = 2.
  • The total cost is 2 + 2 = 4, which is strictly less than budget = 5.
  • The maximum total capacity is capacity[1] + capacity[2] = 5 + 4 = 9.

Β 

Constraints:

  • 1 <= n == costs.length == capacity.length <= 105
  • 1 <= costs[i], capacity[i] <= 105
  • 1 <= budget <= 2 * 105

Solutions

Solution 1: Sorting + Ordered Set

We first filter out all machines with costs less than the budget and sort them by cost in ascending order, recording them in the array \(\textit{arr}\), where \(\textit{arr}[i] = (\textit{costs}[i], \textit{capacity}[i])\). If \(\textit{arr}\) is empty, we cannot buy any machine, so we return \(0\).

Otherwise, we can obtain the machine with the maximum capacity in \(\textit{arr}\) and initialize the answer with this capacity.

Next, we use a two-pointer approach to iterate through pairs of machines in \(\textit{arr}\), using an ordered set \(\textit{remain}\) to maintain the capacities of all currently available machines. Initially, \(\textit{remain}\) contains the capacities of all machines in \(\textit{arr}\).

We use pointers \(i\) and \(j\) pointing to the beginning and end of \(\textit{arr}\), respectively. For each \(i\), we remove \(\textit{arr}[i]\) from \(\textit{remain}\), and then move pointer \(j\) until \(\textit{arr}[i].\textit{cost} + \textit{arr}[j].\textit{cost} < \textit{budget}\). During this process, we remove the machines that do not satisfy the condition from \(\textit{remain}\). At this point, any machine in \(\textit{remain}\) can be bought together with \(\textit{arr}[i]\). We take the machine with the maximum capacity from \(\textit{remain}\), add its capacity to \(\textit{arr}[i]\)'s capacity, and update the answer. Finally, we return the answer.

The time complexity is \(O(n \log n)\), and the space complexity is \(O(n)\), where \(n\) is the number of machines.

 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:
    def maxCapacity(self, costs: List[int], capacity: List[int], budget: int) -> int:
        arr = []
        for a, b in zip(costs, capacity):
            if a < budget:
                arr.append((a, b))
        if not arr:
            return 0
        arr.sort()
        remain = SortedList()
        for i, (_, b) in enumerate(arr):
            remain.add((b, i))
        i, j = 0, len(arr) - 1
        ans = remain[-1][0]
        while i < j:
            remain.discard((arr[i][1], i))
            while i < j and arr[i][0] + arr[j][0] >= budget:
                remain.discard((arr[j][1], j))
                j -= 1
            if remain:
                ans = max(ans, arr[i][1] + remain[-1][0])
            i += 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
class Solution {
    public int maxCapacity(int[] costs, int[] capacity, int budget) {
        List<int[]> arr = new ArrayList<>();
        for (int k = 0; k < costs.length; k++) {
            int a = costs[k], b = capacity[k];
            if (a < budget) {
                arr.add(new int[] {a, b});
            }
        }
        if (arr.isEmpty()) {
            return 0;
        }
        arr.sort(Comparator.comparingInt(o -> o[0]));
        TreeSet<int[]> remain = new TreeSet<>((x, y) -> {
            if (x[0] != y[0]) {
                return x[0] - y[0];
            }
            return x[1] - y[1];
        });
        for (int i = 0; i < arr.size(); i++) {
            remain.add(new int[] {arr.get(i)[1], i});
        }
        int i = 0, j = arr.size() - 1;
        int ans = remain.last()[0];
        while (i < j) {
            remain.remove(new int[] {arr.get(i)[1], i});
            while (i < j && arr.get(i)[0] + arr.get(j)[0] >= budget) {
                remain.remove(new int[] {arr.get(j)[1], j});
                j--;
            }
            if (!remain.isEmpty()) {
                ans = Math.max(ans, arr.get(i)[1] + remain.last()[0]);
            }
            i++;
        }
        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
class Solution {
public:
    int maxCapacity(vector<int>& costs, vector<int>& capacity, int budget) {
        vector<pair<int, int>> arr;
        for (int k = 0; k < costs.size(); k++) {
            int a = costs[k], b = capacity[k];
            if (a < budget) {
                arr.emplace_back(a, b);
            }
        }
        if (arr.empty()) {
            return 0;
        }
        sort(arr.begin(), arr.end());
        multiset<pair<int, int>> remain;
        for (int i = 0; i < arr.size(); i++) {
            remain.insert({arr[i].second, i});
        }
        int i = 0, j = arr.size() - 1;
        int ans = prev(remain.end())->first;
        while (i < j) {
            remain.erase(remain.find({arr[i].second, i}));
            while (i < j && arr[i].first + arr[j].first >= budget) {
                remain.erase(remain.find({arr[j].second, j}));
                j--;
            }
            if (!remain.empty()) {
                ans = max(ans, arr[i].second + prev(remain.end())->first);
            }
            i++;
        }
        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
type Node struct {
    b int
    i int
}

type MaxHeap []Node

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool {
    if h[i].b != h[j].b {
        return h[i].b > h[j].b
    }
    return h[i].i > h[j].i
}
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) {
    *h = append(*h, x.(Node))
}
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func maxCapacity(costs []int, capacity []int, budget int) int {
    arr := make([][2]int, 0)
    for k := 0; k < len(costs); k++ {
        a, b := costs[k], capacity[k]
        if a < budget {
            arr = append(arr, [2]int{a, b})
        }
    }
    if len(arr) == 0 {
        return 0
    }
    sort.Slice(arr, func(i, j int) bool {
        if arr[i][0] != arr[j][0] {
            return arr[i][0] < arr[j][0]
        }
        return arr[i][1] < arr[j][1]
    })
    alive := make([]bool, len(arr))
    h := &MaxHeap{}
    for i := 0; i < len(arr); i++ {
        alive[i] = true
        heap.Push(h, Node{arr[i][1], i})
    }
    i, j := 0, len(arr)-1
    for h.Len() > 0 && !alive[(*h)[0].i] {
        heap.Pop(h)
    }
    ans := (*h)[0].b
    for i < j {
        alive[i] = false
        for i < j && arr[i][0]+arr[j][0] >= budget {
            alive[j] = false
            j--
        }
        for h.Len() > 0 && !alive[(*h)[0].i] {
            heap.Pop(h)
        }
        if h.Len() > 0 {
            if arr[i][1]+(*h)[0].b > ans {
                ans = arr[i][1] + (*h)[0].b
            }
        }
        i++
    }
    return ans
}

Comments