Easy CPP: Sort, binary search, prefix sum
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```cpp []
#define ll long long
class Solution {
public:
    ll maximumCoins(vector<vector<int>>& coins, int k) {
        int n = coins.size();
        sort(coins.begin(), coins.end());
        vector<pair<int, int>> ends;
        for(int i = 0 ; i < n ; i++) {
            ends.push_back({coins[i][1], i});
        }
        vector<ll> ps(n, 0);
        ps[0] = 1LL * (coins[0][1] - coins[0][0] + 1) * coins[0][2];
        for(int i = 1 ; i < n ; i++) {
            ps[i] = ps[i - 1] + 1LL * (coins[i][1] - coins[i][0] + 1) * coins[i][2];
        }
        ll ans = 0;
        for(int i = 0 ; i < n ; i++) {
            int l = coins[i][0], r = l + k - 1;
            pair<int, int> target = {r, 0};
            auto it = upper_bound(ends.begin(), ends.end(), target);
            if(it == ends.end()) {
                --it;
            }
            int idx = (*it).second;
            ll coinsCollected = idx > 0 ? ps[idx - 1] : 0;
            if(i > 0) {
                coinsCollected -= ps[i - 1];
            }
            if(coins[idx][0] <= r) {
                coinsCollected += 1LL * (min(r, coins[idx][1]) - coins[idx][0] + 1) * coins[idx][2];
            }
            ans = max(ans, coinsCollected);
            if(i > 0) {
                r = coins[i][1], l = r - k + 1;
                target = {l, 0};
                it = lower_bound(ends.begin(), ends.end(), target);
                if(it == ends.end()) {
                    --it;
                }
                idx = (*it).second;
                if(coins[idx][0] <= l && l <= coins[idx][1]) {
                    coinsCollected = ps[i];
                    coinsCollected -= ps[idx];
                    coinsCollected += 1LL * (coins[idx][1] - max(coins[idx][0], l) + 1) * coins[idx][2];
                    ans = max(ans, coinsCollected);
                }
            }
        }
        return ans;
    }
};

```
['C++']