PrefixSum and BinarySearch Approach
IntuitionIt can be proved that in order to collect maximum coins you need to start at leftMostPoint of interval or end at rightMostPoint of a given interval in
# Intuition
It can be proved that in order to collect maximum coins you need to start at leftMostPoint of interval or end at rightMostPoint of a given interval in case of distinct division of coins in a given interval.


# Approach
Calculate the prefixSum in order to find totalCoins in O(1) time.
Take two case of starting from leftMost or ending at rightMost for every possible indices.
Maximum of all will give the maxium coins that can be collected.


Example - 
```
Sorted Array [[1,3,2], [5,6,4] , [8,10,1]]
PrefixSum [6,14,17]
startpoints [1,5,8] // array creation is not required
endpoints  [3,6,10] // array creation is not required
k = 4
```

```
For index 0 [1,3,2]
Start at 1 
End = 1+4-1 = 4
lower_bound in endpoints is 6 at index 1
Index = 1
letMostCoins = prefixSum[0] = 6
```

```
For index 0 [1,3,2]
End at 3
Start = 3-4+1 = 0
lower_bound in startpoints is 1 at index 0
rightMostCoins = prefixSum[0] = 6
```

```
For index 1 [5,6,4]
Start at 5
End = 5+4-1 = 8
lower_bound in endpoints is 10 at index 2
leftMostCoins = prefixSum[1] - prefixSum[0] + (8-8+1) * 1 = 14-6+1  = 9
```

```
For index 1 [5,6,4]
End at 6
Start = 6-4+1 = 3
lower_bound in startpoints is 5 at index 1
rightMostCoins = prefixSum[1] - prefixSum[0] + (3-3+1) * 2 = 14-6+2 = 10 
```

```
For index 2 [8,10,1]
Start at 8
End = 8+4-1 = 11
lower_bound in endpoints is 11 at index 3
leftMostCoins = prefixSum[2] - prefixSum[1] + 0 = 17-14 = 3
```

```
For index 2 [8,10,1]
End at 10
Start at 10-4+1 = 7
lower_bound in startpoints is 8 at index 2
rightMostCoins = prefixSum[2] - prefixSum[1] +  0 = 17-14 = 3

```

```
Maximum of all cases {6,6,9,10,3,3} is 10
```

# Complexity
- Time complexity:
O(nlogn)

- Space complexity:
O(n)

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

    long long getLeftMostStartCoins(vector<vector<int>>& coins, int k, vector<long long> &prefixSum, int i, int n) {
        int start = coins[i][0];
        int end = start + k - 1;
        int index = lower_bound(coins.begin(),coins.end(),end,[&](vector<int> &a,int x){
            return a[1] <= x;
        }) - coins.begin();
    
        long long leftCoins = 0;
        if(index > 0 )
            leftCoins += prefixSum[index-1]- (i>0 ? prefixSum[i-1] : 0);
        if(index<n && end >= coins[index][0])
            leftCoins += (end-coins[index][0]+1) * 1LL * coins[index][2];  
        return leftCoins;
    }

    long long getRightMostEndCoins(vector<vector<int>>& coins, int k, vector<long long> &prefixSum, int i, int n) {
        int end = coins[i][1];
        int start = end - k + 1;
        int index = lower_bound(coins.begin(),coins.end(), start,[&](vector<int> &a,int x){
            return a[0] <= x;
        }) - coins.begin();
    
        long long rightCoins = 0;
        rightCoins += prefixSum[i]- (index > 0 ? prefixSum[index-1] : 0);
        if(index >0 && coins[index-1][1] >= start)
            rightCoins += (coins[index-1][1] - start +1) * 1LL * coins[index-1][2];  
        return rightCoins;
    }
};

```
['Binary Search', 'Greedy', 'Prefix Sum', 'C++']