Sorting + PrefixSum + Sliding Window
Intuition
At first, I wanted to solve with sliding window for each position, but I cannot do this because the maximum number of range value is 10^9. This soluti
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- At first, I wanted to solve with sliding window for each position, but I cannot do this because the maximum number of range value is 10^9. This solution will get TLE.
- I found that I could either choose the start position of coins[i] or end position of coins[i]. 
  - This works because starting position and end position cannot be placed in the middle of range at the same time. If the value of starting position range is larger than that of end position, then we can shift to left for more coins.


# Approach
<!-- Describe your approach to solving the problem. -->
- To get the total coins in the range of `[i, j]`, I calculated the prefixSum. If the end position is located in the `j`th range, then we can add all of coins within `[i, j-1]`. 
- Iterate from the start to fix the starting position and from the end to fix the ending position.

# Complexity
- Time complexity: O(NlogN).
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(N)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        const int n = (int)coins.size();
        sort(coins.begin(), coins.end());
        vector<long long> prefix(n+1, 0LL);
        for (int i = 1; i <= n; ++i) {
            prefix[i] += prefix[i-1] + (long long)coins[i-1][2] * (coins[i-1][1] - coins[i-1][0] + 1);
        }

        long long ans = 0LL;
        // from the start;
        int j = 0;
        for (int i = 0; i < n; ++i) {
            int s = coins[i][0];
            int e = s + k - 1;
            while(j < n && coins[j][1] < e) ++j;
            long long curr = prefix[j] - prefix[i];
            if (j < n && coins[j][0] <= e) {
                curr += (long long)coins[j][2] * (e - coins[j][0] + 1);
            }
            ans = max(ans, curr);
        }

        // from the end;
        j = n-1;
        for (int i = n -1; i >= 0; --i) {
            int e = coins[i][1];
            int s = e - k + 1;
            while(j >= 0 && coins[j][0] > s) j--;
            long long curr = prefix[i+1] - prefix[j+1];
            if (j >= 0 && coins[j][1] >= s) {
                curr += (long long)coins[j][2] * (coins[j][1] - s + 1);
            }
            ans = max(ans, curr);
        }
        return ans;
    }
};
```
['C++']