using binary search
Intuitionfinding a valid maximum possible coins amountApproachUsing the binary search as  maximum possible coins amount following increasing propertyComplexity
# Intuition
finding a valid maximum possible coins amount

# Approach
Using the binary search as  maximum possible coins amount following increasing property


# Complexity
- Time complexity: $$O(nlogn)

- Space complexity:
- $$O(n)

# Code
```cpp []
class Solution {
public:
    // bool comp(vector<int> &a, vector<int> &b) {
    //     return a[]
    // }
    int findLeft(vector<vector<int>> &c, int val) {
        int i=0, j = c.size()-1;
        while(i<=j) {
            int mid = (i+j)>>1;
            int l = c[mid][0];
            int r = c[mid][1];
            if(val >= l && val <= r)
                return mid;
            else if(val < l)
                j = mid-1;
            else
                i=mid+1;
        }
        return i;
    }

    bool isSatisfied(vector<long long> &pref, vector<vector<int>> &arr, long long val, int k) {
        long long sum = 0;
        int n = arr.size();
        for(int i=0;i<n;i++) {
            int r = arr[i][1];
            if(r-k <= 0) {
                sum = max(sum, pref[i]);
                continue;
            }
            int indx = findLeft(arr, r-k);
            if(arr[indx][0] > r-k) {
                sum = max(sum, pref[i]-(indx-1>=0?pref[indx-1]:0));
            }
            else {
                // int diff = (r-k)
                sum = max(sum, pref[i]-pref[indx]+(arr[indx][1]-(r-k))*1ll*arr[indx][2]);
            }
        }
        // cout << sum <<  " " << val << " sum value\n";
        if(sum >= val)
            return true;
        sum = 0;
        for(int i=0;i<n;i++) {
            int r = arr[i][0];
            int indx = findLeft(arr, r+k);
            // cout << indx <<  " " << r+k << "\n";
            if(indx >= n) {
                sum = max(sum, pref[n-1]-(i!=0?pref[i-1]:0));
                continue;
            }
            
            // if(indx == i)
            //     sum = max(sum , k*1ll*arr[indx][2]);
            // else 
            if(arr[indx][0] > r+k)
                sum = max(sum, pref[indx-1]-(i!=0?pref[i-1]:0));
            else
                sum = max(sum, pref[indx]-(i==0?0:pref[i-1])-(arr[indx][1]-(r+k)+1)*1ll*arr[indx][2]);
            // cout << sum << "\n";
        }
        return sum>=val;
    } 

    long long maximumCoins(vector<vector<int>>& coins, int k) {
        sort(coins.begin(), coins.end());
        long long high = 1e12;
        long long low = 1;
        long long ans = 0;
        int n = coins.size();
        vector<long long> prefix(n);
        prefix[0] = (coins[0][1]-coins[0][0]+1)*1ll*coins[0][2];
        for(int i=1;i<n;i++) {
            prefix[i] = prefix[i-1]+(coins[i][1]-coins[i][0]+1)*1ll*coins[i][2];
        }
        while(low<=high) {
            long long mid = (low+high)>>1;
            if(isSatisfied(prefix, coins, mid, k)) {
                // cout << mid << "\n";
                ans = max(ans, mid);
                low = mid+1;
            }
            else {
                high = mid-1;
            }
        }
        return ans;
    }
};
```
['C++']