LeetCode-in-Java

3413. 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.

Solution

import java.util.Arrays;

public class Solution {
    public long maximumCoins(int[][] coins, int k) {
        Arrays.sort(coins, (a, b) -> a[0] - b[0]);
        int n = coins.length;
        long res = 0;
        long cur = 0;
        int j = 0;
        for (int[] ints : coins) {
            while (j < n && coins[j][1] <= ints[0] + k - 1) {
                cur += (long) (coins[j][1] - coins[j][0] + 1) * coins[j][2];
                j++;
            }
            if (j < n) {
                long part = (long) Math.max(0, ints[0] + k - 1 - coins[j][0] + 1) * coins[j][2];
                res = Math.max(res, cur + part);
            }
            cur -= (long) (ints[1] - ints[0] + 1) * ints[2];
        }
        cur = 0;
        j = 0;
        for (int[] coin : coins) {
            cur += (long) (coin[1] - coin[0] + 1) * coin[2];
            while (coins[j][1] < coin[1] - k + 1) {
                cur -= (long) (coins[j][1] - coins[j][0] + 1) * coins[j][2];
                j++;
            }
            long part = (long) Math.max(0, coin[1] - k - coins[j][0] + 1) * coins[j][2];
            res = Math.max(res, cur - part);
        }
        return res;
    }
}

This site is open source. Improve this page.