Skip to content

3715. Maximum Coins From K Consecutive Bags

Array Binary Search Greedy Sliding Window Sorting Prefix Sum

Problem - Maximum Coins From K Consecutive Bags

Medium

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.

 

Example 1:

Input: coins = [[8,10,1],[1,3,2],[5,6,4]], k = 4

Output: 10

Explanation:

Selecting bags at positions [3, 4, 5, 6] gives the maximum number of coins: 2 + 0 + 4 + 4 = 10.

Example 2:

Input: coins = [[1,10,3]], k = 2

Output: 6

Explanation:

Selecting bags at positions [1, 2] gives the maximum number of coins: 3 + 3 = 6.

 

Constraints:

  • 1 <= coins.length <= 105
  • 1 <= k <= 109
  • coins[i] == [li, ri, ci]
  • 1 <= li <= ri <= 109
  • 1 <= ci <= 1000
  • The given segments are non-overlapping.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def maximumCoins(self, coins: List[List[int]], k: int) -> int:
        if not coins or k <= 0:
            return 0

        n = len(coins)
        segs = sorted(coins, key=lambda x: x[0])
        starts = [s[0] for s in segs]
        ends   = [s[1] for s in segs]
        amts   = [s[2] for s in segs]

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + (ends[i] - starts[i] + 1) * amts[i]

        def money_up_to(x):
            if x < starts[0]:
                return 0
            idx = bisect.bisect_right(starts, x) - 1
            right = min(ends[idx], x)
            return prefix[idx] + (right - starts[idx] + 1) * amts[idx]

        cands = set()
        for i in range(n):
            cands.add(starts[i])
            cands.add(ends[i] - k + 1)

        best = 0
        for i in cands:
            i = max(1, i)
            best = max(best, money_up_to(i + k - 1) - money_up_to(i - 1))
        return best

Submission Stats:

  • Runtime: 1253 ms (12.28%)
  • Memory: 75.8 MB (5.85%)