3413. Maximum Coins From K Consecutive Bags(62.88%)
Intuition
Represent coin intervals with a difference array-like map.
Flatten the data into positions and their respective coin counts using prefix sums.
Use a s
# Intuition
1. Represent coin intervals with a difference array-like map.
2. Flatten the data into positions and their respective coin counts using prefix sums.
3. Use a sliding window to find the maximum sum of k consecutive positions.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
 1. Use a Map for Coin Changes:
    - Each interval [li, ri] with ci coins is represented by:
        - Adding ci coins to li (coinMap[li] += ci).
        - Subtracting ci coins from ri + 1 (coinMap[ri + 1] -= ci).
    - This creates a map where each key represents a coordinate, and the value
represents how the number of coins changes at that coordinate.

2. Flatten into Prefix Coins:
    - Traverse the map in sorted order of coordinates, maintaining a running
total (currentCoins) of coins at each position.
    - Store these positions and their respective currentCoins in a list
prefixCoins.

3. Apply Sliding Window Technique:
    - Traverse the prefixCoins list while maintaining a sliding window of size
k.
    - For each segment:
        - Add the coins in the current interval to windowSum and update the
window size.
        - If the window size exceeds k, shrink it from the left by subtracting
coins from the start of the window.
    - Keep track of the maximum coins obtained (maxCoins).


# Complexity
- Time complexity: $$O(n+m)$$ 
    - Constructing coinMap: $$O(n)$$, where `n` is the number of intervals in coins.
    - Traversing coinMap: $$O(m)$$, where `m` is the number of unique positions.
    - Sliding window traversal: $$O(m)$$.


- Space complexity: $$O(m)$$

# Code
```cpp []
#define ll long long

class Solution {
public:
    long long maximumCoins(vector<vector<int>>& x, int k) {
        ll ans = 0, n = x.size();

        x.insert(x.begin(), {0});
        sort(x.begin(), x.end());

        vector<ll>pre(n + 1);
        for(int i = 1; i <= n; i++)
            pre[i] = pre[i - 1] + (x[i][1] - x[i][0] + 1) * (ll)x[i][2];


        for(int i = 1; i <= n; i++){
            int l = i + 1 , r = n,  m, o = x[i][0] + k - 1;
            while(l <= r){
                m = l + r >> 1;

                (o >= x[m][0] ? l = m + 1 : r = m - 1);
            }

            if(o >= x[r][1])                              // if the point is covers all the intervals 
                ans = max(ans, pre[r] - pre[i - 1]);
            else                                          // if the point is not covers all the intervals 
                ans = max(ans,pre[r-1]-pre[i-1] + (o - x[r][0] + 1) * (ll)x[r][2]);


            l = 1 , r = i - 1, o = x[i][1] - k + 1;
            while(l <= r){
                m = l  + r >> 1;

                (o <= x[m][1] ? r = m - 1 : l = m + 1);
            }

            if(o <= x[l][0])                              // if the point is covers all the intervals 
                ans = max(ans, pre[i] - pre[l - 1]);
            else                                          // if the point is not covers all the intervals 
                ans = max(ans, pre[i] - pre[l] + (x[l][1] - o + 1) * (ll)x[l][2]);
        }

        return ans;
    }
};
```
```ts []
function maximumCoins(coins: number[][], k: number): number {
    let ans = 0n; // Use BigInt for handling large numbers
    const n = coins.length;

    // Insert a dummy interval at the beginning
    coins.unshift([0, 0, 0]);
    coins.sort((a, b) => a[0] - b[0]); // Sort intervals by start position

    // Prefix sum array
    const pre = new Array<bigint>(n + 1).fill(0n);
    for (let i = 1; i <= n; i++) {
        const [li, ri, ci] = coins[i];
        pre[i] = pre[i - 1] + BigInt((ri - li + 1) * ci);
    }

    for (let i = 1; i <= n; i++) {
        // Binary search for right segments
        let l = i + 1, r = n, o = coins[i][0] + k - 1;
        while (l <= r) {
            const m = Math.floor((l + r) / 2);
            if (o >= coins[m][0]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        if (o >= coins[r][1]) {
            // Covers all intervals
            ans = ans > pre[r] - pre[i - 1] ? ans : pre[r] - pre[i - 1];
        } else {
            // Partially covers the interval
            ans = ans > (pre[r - 1] - pre[i - 1] + BigInt(o - coins[r][0] + 1) * BigInt(coins[r][2]))
                ? ans
                : (pre[r - 1] - pre[i - 1] + BigInt(o - coins[r][0] + 1) * BigInt(coins[r][2]));
        }

        // Binary search for left segments
        l = 1;
        r = i - 1;
        o = coins[i][1] - k + 1;
        while (l <= r) {
            const m = Math.floor((l + r) / 2);
            if (o <= coins[m][1]) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        if (o <= coins[l][0]) {
            // Covers all intervals
            ans = ans > pre[i] - pre[l - 1] ? ans : pre[i] - pre[l - 1];
        } else {
            // Partially covers the interval
            ans = ans > (pre[i] - pre[l] + BigInt(coins[l][1] - o + 1) * BigInt(coins[l][2]))
                ? ans
                : (pre[i] - pre[l] + BigInt(coins[l][1] - o + 1) * BigInt(coins[l][2]));
        }
    }

    return Number(ans); // Convert BigInt back to number
}
```
[c++](https://leetcode.com/problems/maximum-coins-from-k-consecutive-bags/submissions/1500253547/)
[ts](https://leetcode.com/problems/maximum-coins-from-k-consecutive-bags/submissions/1500261221/)
['C++']