1.5hrs after contest ends...
I'm tiredIntuitionI first thought to sort the coins by where they start since that would make iterating through them sensible. Originally I thought to loop thro
I'm tired

# Intuition
I first thought to sort the coins by where they start since that would make iterating through them sensible. Originally I thought to loop through every possibile starting index but that was too slow. Then I thought of course I can just only take ranges that start at the start of a coin range. Except for the end where I would need to check the last k possible spaces as an edge case. But when that wasn't producing the right answer I finally realized that we have to check ranges that start at the start of a coin range AND ranges that end at the end of a coin range. 

Suppose a grabbing range did not match either a start index or an end index of a coin range. Then, moving it right will change the value by a number x (gaining a number y on the right and losing a number z on the left) and moving it left will change the value by a number -x (gaining a number z on the left and losing a number y on the right). So, the max possible coins can always be grabbed in a way that involves matching either the start or the end, because if it did not match either, you can always make a nondecreasing coin move.   

# Approach
1) Sort coins by left index
2) Now that coins are sorted, loop over them to keep track of the cumulative coins at each index bunch. We can use this later to calculate the amount of coins in between two indices in log(m) time where m is the size of coins
3) Loop through coin ranges and calculate how many coins are grabbed when you start the grabbing at the left index of that coin range. Calculate by subtracting the cumulative amount of coins up to but not including the start from the cumulative amount of coins up to and including the end. We use a binary search to add the coins that are "leftover" when the grabbing range contains only part of a coin range.
4) Repeat above except instead of starting at the left index, we now stop at the right index.
5) Return the highest value calculated in steps 3 and 4. 


# Complexity
- Time complexity:
$$O(nlogn)$$ Due to sorting the coins vector and doing binary search inside a loop.

- Space complexity:
$$O(n)$$ due to making the cumCoins vector and also sorting, assuming its not in place

# Code
```cpp []
class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        // Sort coins by li
        // Loop thru coins choosing to start at starts and end at the ends, take max
        // If youre grabbing is in the middle of a range on both sides, moving one way or
        // the other would at least keep the sum the same (if you lose on way, the other way
        // you would gain). From this we conclude it is sufficient to check the edges

        sort(coins.begin(), coins.end(), comp);

        long long ans = 0;
        int n = coins.size();
        int wholeStart = coins[0][0];
        int wholeEnd = coins[n - 1][1];
        int coinsIndex = 0;

        // The amount of coins accumulated before ith zone
        vector<long long> cumCoins; 
        cumCoins.push_back(0);
        
        // Loop thru to make and calc cum coins to make it easy to calc range coins later (see getCoins)
        for(int i = 0; i < coins.size() - 1; i++) {
            cumCoins.push_back((long long) coins[i][2] * (coins[i][1] - coins[i][0] + 1) + cumCoins[cumCoins.size() - 1]);
        }

        // Check start of ranges
        for(int i = 0; i < coins.size(); i++) {
            int startIndex = coins[i][0];
            int endIndex = startIndex + k - 1;
            ans = max(ans, getCoinDiff(coins, cumCoins, endIndex, startIndex));
        }
        
        // Check end of ranges
        for(int i = 0; i < coins.size(); i++) {
            int endIndex = coins[i][1];
            int startIndex = endIndex - k + 1;
            ans = max(ans, getCoinDiff(coins, cumCoins, endIndex, startIndex));
        }

        return ans;
    }

    long long getCoinDiff(vector<vector<int>>& coins, vector<long long>& cumCoins, int e, int s) {
        return getCoins(coins, cumCoins, e) - getCoins(coins, cumCoins, s - 1);
    }

    long long getCoins(vector<vector<int>>& coins, vector<long long>& cumCoins, int index) {
        int low = 0;
        int high = coins.size() - 1;

        int latestI = coins.size();

        while(low <= high) {
            int mid = (low + high) / 2;
            if(index > coins[mid][0]) {
                latestI = mid;
                low = mid + 1;
            }
            else if(index < coins[mid][0]) {
                high = mid - 1;
            }
            else {
                latestI = mid;
                break;
            }
        }

        if(latestI == coins.size()) {
            return 0;
        }

        int totalCoverage = min(coins[latestI][1], index) - coins[latestI][0] + 1;

        return cumCoins[latestI] + (long long) totalCoverage * coins[latestI][2];
    }

    static bool comp(vector<int>& a, vector<int>& b) {
        return a[0] < b[0];
    }
};
```
['C++']