Prefix Sum + Binary Search | Intuition Explained
Intuition

Maximum coins can be achieved by choosing a starting or ending point of some interval. Hence, we check coins for all starting and ending positions.
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- Maximum coins can be achieved by choosing a starting or ending point of some interval. Hence, we check coins for all starting and ending positions.

- For all starting and ending points, we check the reach and calculate number of coins in that reach.

- Also, we maintain a prefix sum array and a suffix sum array to get coins over a range in O(1) time.

- Further, we use binary search to get the index of the interval where we can possibly reach. This reduces the time complexity from O(n) to O(log n).

# 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 []
#define ll long long

class Solution {
public:

    long long mx(long long a, long b){
        if(a>b){
            return a;
        }
        return b;
    }

    long long maximumCoins(vector<vector<int>>& coins, int k) {

        int n=coins.size();
        ll ans=0;
        sort(coins.begin(), coins.end());

        vector<ll> psum(n);
        psum[0]=(ll)(coins[0][2])*(ll)((coins[0][1]-coins[0][0]+1));
        for(int i=1; i<n; i++){
            psum[i]=(ll)psum[i-1]+(ll)coins[i][2]*(ll)(coins[i][1]-coins[i][0]+1);
        }

        vector<ll> ssum(n);
        ssum[n-1]=(ll)coins[n-1][2]*(ll)(coins[n-1][1]-coins[n-1][0]+1);
        for(int i=n-2; i>=0; i--){
            ssum[i]=(ll)ssum[i+1]+(ll)coins[i][2]*(ll)(coins[i][1]-coins[i][0]+1);
        }

        vector<int> startTimes, endTimes;
        for(int i=0; i<n; i++){
            startTimes.push_back(coins[i][0]);
            endTimes.push_back(coins[i][1]);
        }

        //Checking for all starting points
        for(int i=0; i<n; i++){

            int maxReach=coins[i][0]+k-1;

            if(lower_bound(endTimes.begin(), endTimes.end(), maxReach)==endTimes.end()){
                if(i==0){
                    ans=mx(ans, psum[n-1]);
                }
                else{
                    ans=mx(ans, psum[n-1]-psum[i-1]);
                }
                continue;
            }
            int index=lower_bound(endTimes.begin(), endTimes.end(), maxReach) - endTimes.begin();
            
            long long cur=0;
            if(maxReach>=startTimes[index]){
                cur+=(ll)(maxReach-startTimes[index]+1)*(ll)coins[index][2];
            }

            if(index>0){
                if(i==0){
                    cur+=psum[index-1];
                }
                else{
                    cur+=psum[index-1]-psum[i-1];
                }
            }
            ans=mx(ans, cur);
        }

        //Checking for all ending points
        for(int i=n-1; i>=0; i--){

            int minReach=coins[i][1]-k+1;

            if(lower_bound(startTimes.begin(), startTimes.end(), minReach)==startTimes.end()){
                ans=mx(ans, (endTimes[i]-minReach+1)*coins[i][2]);
                continue;
            }
            int index=lower_bound(startTimes.begin(), startTimes.end(), minReach)-startTimes.begin();

            long long cur=0;
            if(index>0 && endTimes[index-1]>=minReach){
                cur+=(ll)(endTimes[index-1]-minReach+1)*(ll)coins[index-1][2];
            }
            if(i==n-1){
                cur+=ssum[index];
            }
            else{
                cur+=ssum[index]-ssum[i+1];
            }
            ans=mx(ans, cur);
        }

        return ans;
    }
};
```
['Binary Search', 'Greedy', 'Sorting', 'Prefix Sum', 'C++']