Step by Step | Conceptually Good | Binary Search + Prefix Sum
Code
# Code
```cpp []
#define ll long long
class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        ll n = coins.size();
        sort(coins.begin(), coins.end());
        vector<ll> p(n, 0);
        p[0] = 1LL * coins[0][2] * (coins[0][1] - coins[0][0] + 1);
        
        for(ll i = 1; i < n; i++){
            p[i] = p[i - 1] + ((1LL * coins[i][2]) * (coins[i][1] - coins[i][0] + 1));
        }

        vector<vector<ll>> v;
        for(ll i = 0; i < n; i++){
            ll p1 = coins[i][0];
            ll p2 = coins[i][1];

            v.push_back({p1, p1 + k - 1});
            v.push_back({max(p1 - k + 1, 1LL), p1});
            v.push_back({p2, p2 + k - 1});
            v.push_back({max(1LL, p2 - k + 1), p2});
        }

        // cout << "# ALL INTERVALS" << endl;
        // for(auto &it : v){
        //     for(auto i : it) cout << i << " ";
        //     cout << endl;
        // }

        ll res = 0;
        for(auto itv : v){
            ll start = itv[0];
            ll end = itv[1];

            // cout << "# NEW INTERVAL" << endl;
            // cout << start << endl;
            // cout << end << endl;

            ll idx1 = -1, idx2 = -1;
            ll lo1 = 0;
            ll hi1 = n - 1;
            while(lo1 <= hi1){
                ll mid = (lo1 + hi1)/2;
                if(start <= coins[mid][1]){
                    idx1 = mid;
                    hi1 = mid - 1;
                }
                else{
                    lo1 = mid + 1;
                }
            }

            ll lo2 = 0;
            ll hi2 = n - 1;
            while(lo2 <= hi2){
                ll mid = (lo2 + hi2)/2;
                if(end >= coins[mid][0]){
                    idx2 = mid;
                    lo2 = mid + 1;
                }
                else{
                    hi2 = mid - 1;
                }
            }
            // idx1, idx1 + 1, ----- , idx2 - 1, idx2 : Prefix sum till this but take care of the boundaries
            // complete prefix sum from idx1 + 1 -> idx2 - 1
            ll ans = 0;
            // cout << idx1 << " : " << idx2 << endl;
            if(idx1 + 1 <= idx2 - 1 && (idx2 - 1 >= 0)){
                ans += (p[idx2 - 1] - p[idx1]);
            }

            // cout << ans << endl;
            if(idx1 == idx2){
                ans += (coins[idx2][2] * (min((ll)coins[idx2][1], end) - max((ll)coins[idx2][0], start) + 1));
            }
            else {
                // cout << "INSIDE" << endl;
                ans += (max(min(end, (ll)coins[idx2][1]) - coins[idx2][0] + 1, 0LL))*coins[idx2][2];
                // cout << ans << endl;
                ans += (max(0LL, coins[idx1][1] - max(start, (ll)coins[idx1][0]) + 1))*coins[idx1][2];
                // cout << ans << endl;
            }
            // cout << "TOTAL COINS : " << ans << endl;
            res = max(res, ans);
        }

        return res;
    }
};
```
['C++']