prefix sum + binary search(es). ~850ms. finished 10m late :/.
IntuitionThere are two options to make an optimal choice
a) collect bags within range of k starting at a left edge of a coin interval
b) collect bags within ran
# Intuition
There are two options to make an optimal choice
a) collect bags within range of k starting at a left edge of a coin interval
b) collect bags within range of k ending at a right edge of a coin interval

# Approach
pre-compute a prefix sum over all coin intervals that stores the total number of coins contained up to (including) the current coin interval

then loop over all coin intervals and evalute that total number of coins contained within option a) and option b) when both are anchored at the current coin interval (i.e. range k starting at current left edge and range k ending at current right edge.)

To compute the total number of coins, we need binary searches to obtain the coin interval at which the total range k ends (option a) or at which the total range k starts (option b)

The challenging part is to correctly add the coins from interval that only partly contribute the the solution.
Recommend visualizing on paper to get past the index madness.

# Complexity
- Time complexity:
$$O(n * log(n))$$ where n is the number of coin intervals

- Space complexity:
$$O(n)$$ e.g. storing the prefix sum

# Code
```python3 []
class Solution:
    def maximumCoins(self, coins: List[List[int]], k: int) -> int:
        coins.sort()
        ls, rs, cs = zip(*coins)

        # precompute prefix over all intervals
        total_coins_prefix = [0] * len(coins)
        curr = 0
        for i, (l, r, c) in enumerate(coins):
            curr += (r-l+1) * c
            total_coins_prefix[i] = curr

        ans = 0
        
        for i, (l, r) in enumerate(zip(ls, rs)):
            #### case 1: range of length k beginning at each interval's left edge
            curr = 0
            if i > 0:
                # subtract total value of intervals before l
                curr -= total_coins_prefix[i-1]
                
            j = bisect_left(ls, l+k+1)-1
            # can add value of all intervals up to (but excluding) this potentially partial interval
            if j > 0:
                curr += total_coins_prefix[j-1]
                
            # now need to handle last partial interval
            last_l, last_r = ls[j], rs[j]
            curr += (min(last_r, l+k-1) - last_l + 1) * cs[j]
            ans = max(ans, curr)

            #### case2: range of length k ending at each interval's right edge
            curr = 0
            # we include up to current box
            curr += total_coins_prefix[i]
                
            j = bisect_left(rs, r-k)
            # need to subtract intervals up to (and including) this potentially partial interval
            curr -= total_coins_prefix[j]
                
            # now need to handle first potentially partial interval
            first_l, first_r = ls[j], rs[j]
            curr += (first_r - max(first_l, r-k+1) + 1) * cs[j]
            ans = max(ans, curr)

        return ans
```
['Python3']