Binary Search prefix sum solution
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 []
class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) 
    {
        long long ans = 0;
        int n = coins.size();
        sort(coins.begin(),coins.end());
        vector<pair<int,int>> v;
        map<int,int> mp;
        vector<long long> pref(n);
        for(int i = 0; i < n; i++)
        {
            pref[i] = (i ? pref[i-1] : 0LL) + 1LL*(coins[i][1]-coins[i][0]+1)*coins[i][2];
            v.push_back({coins[i][0],1});
            v.push_back({coins[i][1],-1});
            mp[coins[i][0]] = i;
            mp[coins[i][1]] = i;
        }
        for(int i = 0; i < v.size(); i++)
        {
            if(v[i].second == 1)
            {
                int tmp = k;
                k--;
                int idx = lower_bound(v.begin(),v.end(),make_pair(v[i].first + k,-1)) - v.begin();
                if(idx == v.size() || v[idx].first > v[i].first + k) idx--;
                if(idx < 0) continue;
                int r = mp[v[idx].first];
                int l = mp[v[i].first];
                long long rsum = pref[r]-(l ? pref[l-1] : 0LL);
                if(v[idx].second == 1)
                {
                    rsum -= 1LL*(coins[r][1]-coins[r][0]+1)*coins[r][2];
                    rsum += 1LL*(v[i].first+k-v[idx].first+1)*(coins[r][2]);
                }
                ans = max(ans,rsum);
                k = tmp;
            }
            else
            {
                int tmp = k;
                k--;
                int idx = lower_bound(v.begin(),v.end(),make_pair(v[i].first-k,-1)) - v.begin();
                if(idx == v.size()) continue;
                int r = mp[v[i].first];
                int l = mp[v[idx].first];
                long long lsum = pref[r]-(l ? pref[l-1] : 0LL);
                if(v[idx].second == -1)
                {
                    lsum -= 1LL*(coins[l][1]-coins[l][0]+1)*coins[l][2];
                    lsum += 1LL*(v[idx].first-(v[i].first-k)+1)*(coins[l][2]);
                }
                ans = max(ans,lsum);
                k = tmp;
            }
        }
        return ans;
    }
};
```
['C++']