✅ [Java / C++] | 34ms | Beats 100%, super easy sliding window approach.
IntuitionThe problem is about finding the maximum number of coins we can collect from k consecutive bags. Using a sliding window approach is optimal because it
# Intuition
The problem is about finding the maximum number of coins we can collect from k consecutive bags. Using a sliding window approach is optimal because it allows us to efficiently compute and update the sum of coins in the window as it moves across the range.
![Screenshot 2025-01-16 at 04.14.28.png](https://assets.leetcode.com/users/images/78221240-8977-489f-a9eb-ea5b5a43b7ab_1737000912.2976456.png)



# Approach
1. Sort the Input: Since the coins ranges may be unsorted, start by sorting them based on their starting coordinates.
2. Sliding Window:
    - Use two pointers (left and right) to represent the bounds of the current window.
    - Maintain a running sum (cur) of coins in the window.
    - For each segment, add coins from the right range if it overlaps with the current window.
    - Remove coins from the left range if it falls outside the current window.
    - Dynamically adjust the start and end of the window based on the constraints of k consecutive bags.
3. Update the Maximum: Track the maximum coins collected during this process.
4. Edge Cases: Handle scenarios where:
    - k exceeds the total number of bags in any range.
    - Sparse ranges where consecutive bags don't overlap.

# Code
```java []
class Solution {
    private static final int S = 32;
    public long maximumCoins(int[][] coins, int k) {
        int n = coins.length;
        // Handle single range case
        if (n == 1) {
            return (long) Math.min(coins[0][1] - coins[0][0] + 1, k) * coins[0][2];
        }
        // Sort ranges by starting position.
        // For faster sorting we combine start and id in long value.
        long[] sorted = new long[n];
        for(int i = 0; i < n; i++) {
            sorted[i] = (long) coins[i][0] << S | i;
        }
        Arrays.sort(sorted);

        long max = 0, cur = 0;
        long start = sorted[0] >> S, end = start + k - 1;

        for (int left = 0, right = 0; right < n;) {
            int[] r = coins[(int)sorted[right]];
            long rs = r[0], re = r[1];
            
            if (end >= re) {
                // Add the entire range at `right` if it fits within the window
                cur += (re - rs + 1) * r[2];
                right++;
                continue;
            }

            // Calculate maximum if the `right` range partially overlaps the window
            max = Math.max(max, rs <= end ? (end - rs + 1) * r[2] + cur : cur);

            int[] l = coins[(int)sorted[left]];
            long le = l[1], newStart = re - k + 1;

            if (newStart <= le) {
                // Adjust for partial overlap of the new window's start with the `left` range
                cur += (re - rs + 1) * r[2] - (newStart - start) * l[2];
                end = re;
                start = newStart;
                right++;
            } else {
                // Shift the window entirely past the `left` range
                left++;
                cur -= (le - start + 1) * l[2];
                start = sorted[left] >> S;
                end = start + k - 1;
            }
        }
        
        return Math.max(max, cur);
    }
}

```
``` C++ []
class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        const int S = 32;
        int n = coins.size();
        // Handle single range case
        if (n == 1) {
            return (long long)min(coins[0][1] - coins[0][0] + 1, k) * coins[0][2];
        }

        // Using raw array for faster sorting
        long long* sorted = new long long[n];
        for (int i = 0; i < n; i++) {
            sorted[i] = ((long long)coins[i][0] << S) | i;
        }
        sort(sorted, sorted + n);

        long long maxCoins = 0, cur = 0;
        long long start = sorted[0] >> S, end = start + k - 1;
        
        for (int left = 0, right = 0; right < n;) {
            auto& r = coins[(int)sorted[right]];
            long long rs = r[0], re = r[1];

            if (end >= re) {
                // Add the entire range at `right` if it fits within the window
                cur += (re - rs + 1) * r[2];
                right++;
                continue;
            }
            // Calculate maximum if the `right` range partially overlaps the window
            maxCoins = max(maxCoins, rs <= end ? (end - rs + 1) * r[2] + cur : cur);

            auto& l = coins[(int)sorted[left]];
            long long le = l[1], newStart = re - k + 1;
            if (newStart <= le) {
                // Adjust for partial overlap of the new window's start with the `left` range
                cur += (re - rs + 1) * r[2] - (newStart - start) * l[2];
                end = re;
                start = newStart;
                right++;
            } else {
                // Shift the window entirely past the `left` range
                left++;
                cur -= (le - start + 1) * l[2];
                start = sorted[left] >> S;
                end = start + k - 1;
            }
        }
        return max(maxCoins, cur);
    }
};
```

['Sliding Window', 'C++', 'Java']