Maximum total from optimal activation order

Array Two Pointers Greedy Sorting Heap (Priority Queue)

33.0% acceptance

Feb 25, 2026

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 element at index i, it adds value[i] to the total activation value. 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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_total(value: Vec<i32>, limit: Vec<i32>) -> i64 {
    let n = value.len();
    // Key insight: When processing elements in ascending limit order, deactivations
    // free active count slots. An element with limit L gets deactivated when active
    // count reaches L, returning its slot. This means the constraint is simply:
    // from each group with limit L, at most L elements can be activated.
    //
    // Algorithm:
    // 1. Group elements by limit.
    // 2. From each group with limit L, take the top min(|group|, L) values.
    // 3. Sum all selected values.
    
    let mut by_limit: Vec<Vec<i32>> = vec![vec![]; n + 2];
    for i in 0..n {
      by_limit[limit[i] as usize].push(value[i]);
    }
    
    let mut result = 0i64;
    for l in 1..=n {
      let group = &mut by_limit[l];
      group.sort_unstable_by(|a, b| b.cmp(a)); // sort descending
      let take = l.min(group.len());
      for i in 0..take {
        result += group[i] as i64;
      }
    }
    result
  }
}