Maximize points after choosing k tasks

Array Greedy Sorting Heap (Priority Queue)

59.9% acceptance

Feb 25, 2026

You are given two integer arrays, technique1 and technique2, each of length n, where n represents the number of tasks to complete. If the ith task is completed using technique 1, you earn technique1[i] points. If it is completed using technique 2, you earn technique2[i] points. You are also given an integer k, representing the minimum number of tasks that must be completed using technique 1. You must complete at least k tasks using technique 1 (they do not need to be the first k tasks). The remaining tasks may be completed using either technique. Return an integer denoting the maximum total points you can earn.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_points(technique1: Vec<i32>, technique2: Vec<i32>, k: i32) -> i64 {
    let n = technique1.len();
    let k = k as usize;
    let mut base = 0i64;
    let mut penalties: Vec<i64> = Vec::new();
    let mut t1_count = 0usize;
    for i in 0..n {
      if technique1[i] >= technique2[i] {
        base += technique1[i] as i64;
        t1_count += 1;
      } else {
        base += technique2[i] as i64;
        penalties.push((technique2[i] - technique1[i]) as i64);
      }
    }
    if t1_count >= k { return base; }
    penalties.sort();
    let need = k - t1_count;
    base - penalties[..need].iter().sum::<i64>()
  }
}