Skip to main content
Back to problems
#3413
Medium Algorithms

Maximum coins from k consecutive bags

Array Binary Search Greedy Sliding Window Sorting Prefix Sum
24.5% acceptance
Feb 25, 2026
197
27
There are an infinite amount of bags on a number line, one bag for each coordinate. Some of these bags contain coins. You are given a 2D array coins, where coins[i] = [li, ri, ci] denotes that every bag from li to ri contains ci coins. The segments that coins contain are non-overlapping. You are also given an integer k. Return the maximum amount of coins you can obtain by collecting k consecutive bags.

Solution

Rust
Time O(n log n)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn maximum_coins(mut coins: Vec<Vec<i32>>, k: i32) -> i64 {
    coins.sort_by_key(|c| c[0]);
    let n = coins.len();
    let k = k as i64;
    // prefix[i] = total coins in segments [0..i)
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + (coins[i][1] - coins[i][0] + 1) as i64 * coins[i][2] as i64;
    }
    let compute = |l: i64| -> i64 {
      let r = l + k - 1;
      let left_idx = coins.partition_point(|c| (c[1] as i64) < l);
      let right_idx = coins.partition_point(|c| (c[0] as i64) <= r);
      if left_idx >= right_idx { return 0; }
      let mut total = prefix[right_idx] - prefix[left_idx];
      let ll = coins[left_idx][0] as i64;
      let lc = coins[left_idx][2] as i64;
      if ll < l { total -= (l - ll) * lc; }
      let rr = coins[right_idx - 1][1] as i64;
      let rc = coins[right_idx - 1][2] as i64;
      if rr > r { total -= (rr - r) * rc; }
      total
    };
    let mut ans = 0i64;
    for c in &coins {
      ans = ans.max(compute(c[0] as i64));
      let l2 = c[1] as i64 - k + 1;
      if l2 > 0 { ans = ans.max(compute(l2)); }
    }
    ans
  }
}