Maximum Coins From K Consecutive Bags

• Identify Candidate Start Positions: The total number of coins in a window of k bags changes only when the window's start or end crosses the boundary of a coin interval. This suggests that the optimal window likely starts at a position related to these boundaries. A reasonable set of candidate start positions for the window [s, s+k-1] are s = l_i or s = r_i - k + 1 for every given interval [l_i, r_i, c_i].
• Iterate and Calculate: The algorithm iterates through each of these O(N) candidate start positions.
• Summation: For each candidate start position s, it calculates the total coins in the window [s, s+k-1]. This is done by iterating through all N coin intervals and summing up the contributions from each interval that overlaps with the window.
• Overlap Calculation: The contribution of an interval [l_j, r_j, c_j] is c_j multiplied by the length of the intersection between [s, s+k-1] and [l_j, r_j].
• Track Maximum: The algorithm keeps track of the maximum sum found across all candidate windows and returns it as the result.

This method is based on a brute-force check over a reduced search space. Instead of checking every possible start position on the number line (which is infinite), we only check positions that are 'critical'.

1. Generate Candidate Start Positions: We create a list of candidate start positions. For each interval [l_i, r_i, c_i], the critical start points for a window of size k are l_i (aligning the window's start with the interval's start) and r_i - k + 1 (aligning the window's end with the interval's end). We collect all such unique, positive positions.

2. Calculate Sum for Each Candidate: For each candidate start position s, we calculate the total coins in the window [s, s + k - 1]. This is done by iterating through all N original coin intervals [l_j, r_j, c_j]. For each interval, we find the length of its overlap with our window [s, s + k - 1]. The overlap length is max(0, min(s + k - 1, r_j) - max(s, l_j) + 1). We multiply this length by c_j and add it to the total for the current window.

3. Find Maximum: We maintain a variable max_coins and update it with the highest total found among all candidate windows.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public long maximumCoins(int[][] coins, int k) {6        Set<Long> candidates = new HashSet<>();7        for (int[] coin : coins) {8            long l = coin[0];9            long r = coin[1];10            candidates.add(l);11            if (r - k + 1 > 0) {12                candidates.add(r - k + 1);13            }14        }15 16        long maxTotalCoins = 0;17 18        for (long startPos : candidates) {19            long endPos = startPos + k - 1;20            long currentTotalCoins = 0;21            for (int[] coin : coins) {22                long l = coin[0];23                long r = coin[1];24                long c = coin[2];25 26                long overlapStart = Math.max(startPos, l);27                long overlapEnd = Math.min(endPos, r);28 29                if (overlapStart <= overlapEnd) {30                    long overlapLength = overlapEnd - overlapStart + 1;31                    currentTotalCoins += overlapLength * c;32                }33            }34            maxTotalCoins = Math.max(maxTotalCoins, currentTotalCoins);35        }36 37        return maxTotalCoins;38    }39}