[Python3] binary search 
IntuitionThis is essentially a line sweep problem. However, due to the large values, one cannot calcualte the numbers naively. Instead, we could leverage on pre
# Intuition
This is essentially a line sweep problem. However, due to the large values, one cannot calcualte the numbers naively. Instead, we could leverage on prefix sum and binary search to make the calculations more efficiently. 

# Approach
We first sort `coins` and calculate the prefix sum of coins. Due to the nature that the coins are constant in a given interval, it is guaranteed that the desired interval of size `k` will have the entire left-most interval or right-most interval unless `k` is not enough to cover an entire interval. As a result, we can collect the right point of the candidate interval. Given an interval `[l, r]`, the points to be considered are `l+k-1` and `r`. The first corresponds to the interval being the left-most one and the second correcsponds to the interval being the right-most one. 

In addition, we need a function to calculate the total number of points before a given point (say `x`). Using the prefix sum, this can be calculated in `log(N)` time. See the code for more detail. 

# Complexity
- Time complexity: `O(NlogN)`
- Space complexity: `O(N)`

# Code
```python3 []
class Solution:
    def maximumCoins(self, coins: List[List[int]], k: int) -> int:
        coins.sort()
        ans = 0
        prefix = [0]
        vals = []
        for l, r, c in coins: 
            prefix.append(prefix[-1] + c*(r-l+1))
            vals.extend([l+k-1, r])
            
        def fn(x): 
            """Return """
            i = bisect_right(coins, x, key=lambda x: x[0])-1
            if i < 0: return 0 
            return prefix[i] + (min(x, coins[i][1]) - coins[i][0] + 1)*coins[i][2]
        
        return max(fn(r) - fn(r-k) for r in sorted(vals))
```
['Python3']