Perfectly Explained Code || With Proof || Greedy Approach || O(N logN) Time
IntuitionTake any subarray of length k to maximize coins, I  thought either start at l[i] or r[i] but that seemed to be incorrect, later on I thought to also co
# Intuition
Take any subarray of length k to maximize coins, I  thought either start at l[i] or r[i] but that seemed to be incorrect, later on I thought to also consider the fact that either end at l[i] or r[i], then I proved it (check out in code), that it was the approach required.

# Approach
Explained through comments in the code.

# Complexity
- Time complexity:
$$O(NlogN)$$ where N is the number of intervals
Analysis : O(NlogN) for sorting + O(N * 4 * logN) during the iteration

- Space complexity:
$$O(n)$$ for prefix sum array

# Code
```cpp []
class Solution {
public:
    long long maximumCoins(vector<vector<int>>& a, int k) {
        // l, r, c
        sort(a.begin(), a.end());   // sorted by starting point

        int n = a.size();

        vector<long long> coins(n, 0); // prefix sum of coins till ith interval
        for (int i = 0; i < n; ++i) {
            long long l = a[i][0], r = a[i][1], c = a[i][2];
            coins[i] += (r - l + 1) * c + (i > 0 ? coins[i - 1] : 0);
        }

        auto sum = [&](int l, int r) -> long long {
            // get sum of coins from l-th interval to r-th interval
            long long ans = 0;
            if (l <= r) {
                ans += coins[r];
                if (l > 0)
                    ans -= coins[l - 1];
            }
            return ans;
        };

        long long maxScore = 0;
        for (int i = 0; i < n; ++i) {
            int l = a[i][0], r = a[i][1], c = a[i][2];

            // start from l
            // l to l+k-1
            int index = upper_bound(a.begin(), a.end(), vector<int>({l + k, 0, 0})) - a.begin() - 1; // index of interval in which l+k-1 definitely lies
            long long score = 0;
            if (index >= 0) {
                // take coins from l[index] to l+k-1, but l+k-1 can be > end point of this interval so take min [as l+k-1 can be in a position where no coin is present]
                score += (long long)(min(a[index][1], l + k - 1) - a[index][0] + 1) * a[index][2];
            }
            // we can take all coins from ith interval to (index-1)th interval
            score += sum(i, index - 1);
            maxScore = max(maxScore, score);

            // end at l
            // l-k+1 to l
            index = lower_bound(a.begin(), a.end(), vector<int>({l - k + 1, 0, 0})) - a.begin() - 1; // index of interval where l-k+1 may lie, we are 100% sure that index+1 interval definitely consist of l-k+1
            score = 0;
            if (index >= 0) {
                // take coins from l-k+1 to r[index], but l-k+1 can be in a position where there is 0 coin, so take max
                // we have taken max with 0 too because of the reason that l-k+1 is not in this interval, so we don't have to consider coins of this interval
                score += max(0ll, (long long)(a[index][1] - max(l - k + 1, a[index][0]) + 1)) * a[index][2];
            }
            // take all coins from index+1 to i-1 as it covers the range of l-k+1 to l-1 and for l, we know there are c coins here, so add that
            score += sum(index + 1, i - 1) + c;
            maxScore = max(maxScore, score);

            // start from r
            // r to r+k-1
            index = upper_bound(a.begin(), a.end(), vector<int>({r + k, 0, 0})) - a.begin() - 1; // interval where r+k-1 lies
            score = 0;
            if (index > i) {
                // this interval must lie ahead of current interval as 'r' is the only point in this interval and we move ahead after this
                // take coins from l[index] to r+k-1
                score += (long long)(min(a[index][1], r + k - 1) - a[index][0] + 1) * a[index][2];
            }
            // take all coins from i+1 to index-1 and c coins from ith interval as only 'r' is inside ith interval and we have considered (index)th interval earlier
            score += sum(i + 1, index - 1) + c;
            maxScore = max(maxScore, score);

            // end at r
            // l-k+1 to l
            index = lower_bound(a.begin(), a.end(), vector<int>({r - k + 1, 0, 0})) - a.begin() - 1; // interval where r-k+1 may lie or in next interval it lies
            score = 0;
            if (index >= 0) {
                // take all coins from r-k+1 to r[index]
                score += max(0ll, (long long)(a[index][1] - max(r - k + 1, a[index][0]) + 1)) * a[index][2];
            }
            // take all coins from index+1 to i interval
            score += sum(index + 1, i);
            maxScore = max(maxScore, score);
        }

        // WHY THIS WORKS ?
        // Let's prove by contradiction : Suppose there exists two intervals [li, ri] and [lj, rj] (li <= ri < lj <= rj) which give max coins if we start at 
        // li < x < ri and end at lj < x + k - 1 < rj, here 3 cases arise : 
        // 1. ci > cj -> its better to shift our range towards [li, ri] as the change would be +ci-cj and stop when we reach x = li
        // 2. ci = cj -> take all coins in [li, ri] and take some from [lj, rj]
        // 3. ci < cj -> its better to shift our range towards [lj, rj] as the change would be +cj-ci and stop when we reach x+k-1 = rj
        // Hence, we should either start at l, end at l, or do same with r for all intervals [l,r]
        return maxScore;
    }
};
```

# Improved Version
As suggested by @ruhlmarkus02 in the comments that we don't need to take the cases when our range ends at l or starts from r as it won't affect our answer. Proof is similar to what I proved earlier, you can notice there too, we either start at l[i] or end at r[i] and that's it whats needed for solving this problem.

So, just remove the part of code where we end at l and also the part where we start from r.

The time complexity would remain same, but time utilized would be reduced as here will be only 2 upper bound calls (instead of 4).


['Binary Search', 'Greedy', 'Prefix Sum', 'C++']