Skip to content

3645. Maximum Total from Optimal Activation Order

Description

You are given two integer arrays value and limit, both of length n.

Initially, all elements are inactive. You may activate them in any order.

  • To activate an inactive element at index i, the number of currently active elements must be strictly less than limit[i].
  • When you activate the element at index i, it adds value[i] to the total activation value (i.e., the sum of value[i] for all elements that have undergone activation operations).
  • After each activation, if the number of currently active elements becomes x, then all elements j with limit[j] <= x become permanently inactive, even if they are already active.

Return the maximum total you can obtain by choosing the activation order optimally.

 

Example 1:

Input: value = [3,5,8], limit = [2,1,3]

Output: 16

Explanation:

One optimal activation order is:

Step Activated i value[i] Active Before i Active After i Becomes Inactive j Inactive Elements Total
1 1 5 0 1 j = 1 as limit[1] = 1 [1] 5
2 0 3 0 1 - [1] 8
3 2 8 1 2 j = 0 as limit[0] = 2 [0, 1] 16

Thus, the maximum possible total is 16.

Example 2:

Input: value = [4,2,6], limit = [1,1,1]

Output: 6

Explanation:

One optimal activation order is:

Step Activated i value[i] Active Before i Active After i Becomes Inactive j Inactive Elements Total
1 2 6 0 1 j = 0, 1, 2 as limit[j] = 1 [0, 1, 2] 6

Thus, the maximum possible total is 6.

Example 3:

Input: value = [4,1,5,2], limit = [3,3,2,3]

Output: 12

Explanation:

One optimal activation order is:​​​​​​​​​​​​​​

Step Activated i value[i] Active Before i Active After i Becomes Inactive j Inactive Elements Total
1 2 5 0 1 - [ ] 5
2 0 4 1 2 j = 2 as limit[2] = 2 [2] 9
3 1 1 1 2 - [2] 10
4 3 2 2 3 j = 0, 1, 3 as limit[j] = 3 [0, 1, 2, 3] 12

Thus, the maximum possible total is 12.

 

Constraints:

  • 1 <= n == value.length == limit.length <= 105
  • 1 <= value[i] <= 105​​​​​​​
  • 1 <= limit[i] <= n

Solutions

Solution 1

Thinking

Activating a value consumes a slot bounded by its \(\textit{limit}\), and items that share a limit compete for those slots.

Group by \(\textit{limit}\). Inside a group at most \(\textit{limit}\) values may be kept, so retain the largest ones.

Groups are independent: sort each list and sum the last \(\textit{lim}\) entries. Distinct limits do not constrain one another.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maxTotal(self, value: List[int], limit: List[int]) -> int:
        g = defaultdict(list)
        for v, lim in zip(value, limit):
            g[lim].append(v)
        ans = 0
        for lim, vs in g.items():
            vs.sort()
            ans += sum(vs[-lim:])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public long maxTotal(int[] value, int[] limit) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int i = 0; i < value.length; ++i) {
            g.computeIfAbsent(limit[i], k -> new ArrayList<>()).add(value[i]);
        }
        long ans = 0;
        for (var e : g.entrySet()) {
            int lim = e.getKey();
            var vs = e.getValue();
            vs.sort((a, b) -> b - a);
            for (int i = 0; i < Math.min(lim, vs.size()); ++i) {
                ans += vs.get(i);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    long long maxTotal(vector<int>& value, vector<int>& limit) {
        unordered_map<int, vector<int>> g;
        int n = value.size();
        for (int i = 0; i < n; ++i) {
            g[limit[i]].push_back(value[i]);
        }
        long long ans = 0;
        for (auto& [lim, vs] : g) {
            sort(vs.begin(), vs.end(), greater<int>());
            for (int i = 0; i < min(lim, (int) vs.size()); ++i) {
                ans += vs[i];
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func maxTotal(value []int, limit []int) (ans int64) {
    g := make(map[int][]int)
    for i := range value {
        g[limit[i]] = append(g[limit[i]], value[i])
    }
    for lim, vs := range g {
        slices.SortFunc(vs, func(a, b int) int { return b - a })
        for i := 0; i < min(lim, len(vs)); i++ {
            ans += int64(vs[i])
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function maxTotal(value: number[], limit: number[]): number {
    const g = new Map<number, number[]>();
    for (let i = 0; i < value.length; i++) {
        if (!g.has(limit[i])) {
            g.set(limit[i], []);
        }
        g.get(limit[i])!.push(value[i]);
    }
    let ans = 0;
    for (const [lim, vs] of g) {
        vs.sort((a, b) => b - a);
        ans += vs.slice(0, lim).reduce((acc, v) => acc + v, 0);
    }
    return ans;
}

Comments