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}

• Event Points and Segments: First, we process the coins array to find all 'event points'. For each interval [l, r, c], l is an event point where the number of coins per bag increases by c, and r+1 is an event point where it decreases by c. We use a map (like TreeMap in Java) to store the net change at each unique position.
• Build Segments: By iterating through the sorted event points, we can construct a list of contiguous segments on the number line. Each segment [p_i, p_{i+1}-1] has a constant number of coins per bag, which we can calculate by accumulating the changes from the event points.
• Prefix Sums: We then build a prefix sum array over these segments. prefix_sum[i] will store the total number of coins from the beginning of the first segment up to the start of the i-th segment. This allows for quick calculation of the total coins over a large range of segments.
• Identify Candidate Windows: The optimal window [s, s+k-1] must start or end at an event point. Thus, the candidate start positions s are p_j or p_j - k + 1 for each event point p_j.
• Query for Sum: For each candidate start s, we calculate the sum of coins in [s, s+k-1] by using a helper function query(p). This function calculates the total coins from the beginning up to position p. The sum for the window is then query(s+k-1) - query(s-1). The query function uses binary search on the segment positions and the prefix sum array to compute the result in O(log N) time.
• Find Maximum: We find the maximum sum among all candidates.

This approach optimizes the calculation for each candidate window from O(N) down to O(log N), resulting in a much faster overall algorithm.

1. Create Event Points: We use a TreeMap to store the change in coins per bag at each interval boundary. For each [l, r, c], we do map[l] += c and map[r+1] -= c. The TreeMap automatically keeps the points sorted and aggregates changes at the same position.

2. Construct Segments and Prefix Sums: We iterate through the TreeMap to build an explicit list of segments. Let's say the sorted unique positions are p_0, p_1, ..., p_m. We can determine the constant number of coins C_i in each segment [p_i, p_{i+1}-1]. Simultaneously, we can build a prefix sum array, prefix_sum[i], storing the total coins from p_0 up to p_i-1.

3. Identify Candidate Start Positions: The set of critical start positions for a window of size k are p_i and p_i - k + 1 for each event point p_i.

4. Efficiently Calculate Window Sum: We create a helper function, say getSum(p), which calculates the total coins in all bags from position 1 to p. This function works by first using binary search to find which segment p falls into. Then, it uses the pre-calculated prefix sum to get the total coins up to the start of that segment and adds the contribution from the partial segment.

5. Evaluate Candidates: For each candidate start position s > 0, the window is [s, s+k-1]. The total coins are calculated as getSum(s+k-1) - getSum(s-1). We track the maximum value found.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.HashSet;4import java.util.List;5import java.util.Map;6import java.util.Set;7import java.util.TreeMap;8 9class Solution {10    public long maximumCoins(int[][] coins, int k) {11        Map<Long, Long> delta = new TreeMap<>();12        for (int[] coin : coins) {13            long l = coin[0];14            long r = coin[1];15            long c = coin[2];16            delta.put(l, delta.getOrDefault(l, 0L) + c);17            delta.put(r + 1, delta.getOrDefault(r + 1, 0L) - c);18        }19 20        List<Long> pos = new ArrayList<>();21        List<Long> segmentCoins = new ArrayList<>();22        long currentCoinsPerBag = 0;23        long lastPos = 1;24 25        for (Map.Entry<Long, Long> entry : delta.entrySet()) {26            long p = entry.getKey();27            if (p > lastPos) {28                pos.add(lastPos);29                segmentCoins.add(currentCoinsPerBag);30            }31            currentCoinsPerBag += entry.getValue();32            lastPos = p;33        }34        pos.add(lastPos);35        segmentCoins.add(currentCoinsPerBag);36 37        int n = pos.size();38        long[] prefixSum = new long[n + 1];39        prefixSum[0] = 0;40        for (int i = 0; i < n - 1; i++) {41            prefixSum[i + 1] = prefixSum[i] + (pos.get(i + 1) - pos.get(i)) * segmentCoins.get(i);42        }43        prefixSum[n] = prefixSum[n-1];44 45        Set<Long> candidates = new HashSet<>();46        for (long p : delta.keySet()) {47            candidates.add(p);48            if (p - k > 0) {49                candidates.add(p - k);50            }51        }52        if (!candidates.contains(1L)) candidates.add(1L);53 54        long maxCoins = 0;55        for (long start : candidates) {56            if (start <= 0) continue;57            long end = start + k - 1;58            maxCoins = Math.max(maxCoins, getSum(end, pos, segmentCoins, prefixSum) - getSum(start - 1, pos, segmentCoins, prefixSum));59        }60 61        return maxCoins;62    }63 64    private long getSum(long p, List<Long> pos, List<Long> segmentCoins, long[] prefixSum) {65        if (p <= 0) return 0;66        67        int i = Collections.binarySearch(pos, p + 1);68        i = (i < 0) ? (-i - 1) - 1 : i - 1;69 70        if (i < 0) return 0;71 72        long sum = prefixSum[i];73        sum += (p - pos.get(i) + 1) * segmentCoins.get(i);74        return sum;75    }76}