Maximum total sum with threshold constraints

Array Greedy Sorting Heap (Priority Queue)

83.5% acceptance

Mar 31, 2026

You are given two integer arrays nums and threshold, both of length n. Starting at step = 1, you perform the following repeatedly: Choose an unused index i such that threshold[i] <= step. If no such index exists, the process ends. Add nums[i] to your running total. Mark index i as used and increment step by 1. Return the maximum total sum you can obtain by choosing indices optimally.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;

impl Solution {
  pub fn max_sum(nums: Vec<i32>, threshold: Vec<i32>) -> i64 {
    let n = nums.len();
    let mut pairs: Vec<(i32, i32)> = threshold.into_iter().zip(nums.into_iter()).collect();
    pairs.sort_unstable();
    let mut heap = BinaryHeap::new();
    let mut total = 0i64;
    let mut j = 0;
    for step in 1..=n as i32 {
      while j < n && pairs[j].0 <= step {
        heap.push(pairs[j].1 as i64);
        j += 1;
      }
      if let Some(val) = heap.pop() {
        total += val;
      } else {
        break;
      }
    }
    total
  }
}