C++ Bruteforce-sorta + Binary Search
Complexity

Time complexity: O(n∗log(n))


Space complexity: O(n)

Code
# Complexity
- Time complexity: $O(n*log(n))$

- Space complexity: $O(n)$

# Code
```cpp []
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        sort(coins.begin(), coins.end());

        int n = coins.size();
        vector pre(n, 0LL);
        // pre[i] = prefix sum of the sum of all bags in coins
        pre[0] = (long long) (coins[0][1] - coins[0][0] + 1) * coins[0][2];
        for(int i = 1; i < n; i++) {
            pre[i] = (long long) (coins[i][1] - coins[i][0] + 1) * coins[i][2];
            pre[i] += pre[i - 1];
        }

        set<int> check;
        for(auto& c : coins) {
            // consider trying to take all bags of C as the first bag and last bag
            check.insert(c[0]);
            if(c[1] - k + 1 > 0)
                check.insert(c[1] - k + 1);
        }
        check.insert(1);
        long long ans = 0;
        for(int x : check) {
            // bisect for left and right i
            int l = 0, r = n-1;
            bool found = false; int mostValid = -1;
            while(l <= r) {
                int m = (l + r) / 2;
                if(coins[m][0] <= x && x <= coins[m][1]) {
                    l = r = m;
                    found = true;
                    break;
                }else if(x < coins[m][0]) {
                    r = m - 1;
                    mostValid = m;
                }else if(coins[m][1] < x) {
                    l = m + 1;
                }
            }
            int firstBag = found ? l : mostValid;

            int end = x + k - 1;
            l = 0, r = n-1;
            found = false, mostValid = -1;
            while(l <= r) {
                int m = (l + r) / 2;
                if(coins[m][0] <= end && end <= coins[m][1]) {
                    l = r = m;
                    found = true;
                    break;
                }else if(end < coins[m][0]) {
                    r = m - 1;
                }else if(coins[m][1] < end) {
                    l = m + 1;
                    mostValid = m;
                }
            }

            int lastBag = found ? l : mostValid;
            if(firstBag == -1 || lastBag == -1) continue;
            if(firstBag == lastBag) {
                int y = firstBag;
                long long sum = (long long) coins[y][2] * (min(coins[y][1], x + k - 1) - max(coins[y][0], x) + 1);
                ans = max(ans, sum);
            }else {
                 int range = coins[lastBag][1] - x + 1;
                long long midSum = (firstBag + 1 <= lastBag - 1) ? pre[lastBag - 1] - pre[firstBag] : 0;
                // firstBag take from x -> r
                // lastBag take from l -> x + k - 1
    
                long long sum = 0;
                sum += 1LL * (coins[firstBag][1] - max(x, coins[firstBag][0]) + 1) * coins[firstBag][2];
                sum += 1LL * (min(x + k - 1, coins[lastBag][1]) - coins[lastBag][0] + 1) * coins[lastBag][2];
                sum += midSum;
                ans = max(ans, sum);   
            }
        }
        return ans;
    }
};
```
['C++']