Binary Search || Beats 100.00%
ApproachAn optimal starting position for k consecutive bags will be either li or ri - k + 1.Code
# Approach
<h3>An optimal starting position for k consecutive bags will be either li or ri - k + 1.</h3>


# Code
```cpp []
#define ll long long

class Solution {
public:
    long long maximumCoins(vector<vector<int>>& x, int k) {
        ll ans = 0, n = x.size();

        x.insert(x.begin(), {0});
        sort(x.begin(), x.end());

        vector<ll>pre(n + 1);
        for(int i = 1; i <= n; i++)
            pre[i] = pre[i - 1] + (x[i][1] - x[i][0] + 1) * (ll)x[i][2];


        for(int i = 1; i <= n; i++){
            int l = i + 1 , r = n,  m, o = x[i][0] + k - 1;
            while(l <= r){
                m = l + r >> 1;

                (o >= x[m][0] ? l = m + 1 : r = m - 1);
            }

            if(o >= x[r][1])                              // if the point is covers all the intervals 
                ans = max(ans, pre[r] - pre[i - 1]);
            else                                          // if the point is not covers all the intervals 
                ans = max(ans,pre[r-1]-pre[i-1] + (o - x[r][0] + 1) * (ll)x[r][2]);


            l = 1 , r = i - 1, o = x[i][1] - k + 1;
            while(l <= r){
                m = l  + r >> 1;

                (o <= x[m][1] ? r = m - 1 : l = m + 1);
            }

            if(o <= x[l][0])                              // if the point is covers all the intervals 
                ans = max(ans, pre[i] - pre[l - 1]);
            else                                          // if the point is not covers all the intervals 
                ans = max(ans, pre[i] - pre[l] + (x[l][1] - o + 1) * (ll)x[l][2]);
        }

        return ans;
    }
};
```
![hhh.png](https://assets.leetcode.com/users/images/f96694bb-97ed-4614-b21c-f026fc74bfe5_1733641265.743601.png)
['Binary Search', 'Greedy', 'Prefix Sum', 'C++']