Sliding window with a lot of corner cases
IntuitionConstraints won't let us slide the whole coordinate line. Let's slide intervals instead.ApproachFirst, sort the intervals to process them in order.We h
# Intuition
Constraints won't let us slide the whole coordinate line. Let's slide intervals instead.

# Approach
First, sort the intervals to process them in order.

We have 5 different options in general.
1. Length of an interval is more than `k`.
2. Current window length is less than `k`, but we can fill it with current interval to be equal to `k`.
3. After length of the window extended `k` we can throw leftmost intervals and `k` can be equal to window length.
4. After removal window can become less than `k` in length. We can pick a part of next to leftmost interval.
5. Or we can pick the whole next to leftmost interval and part of current rightmost.

Carefully calculating all these cases - and voila!

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

- Space complexity:
$$O(1)$$

# Code
```java []
class Solution {
    public long maximumCoins(int[][] coins, int k) {
        Arrays.sort(coins, (a, b) -> Integer.compare(a[0], b[0]));
        long max = 0, curr = 0;
        int start = 0;
        for (int i = 0; i < coins.length; i++) {
            int[] c = coins[i];
            int len = c[1] - c[0] + 1, window = c[0] - coins[start][0];
            if (len >= k) {
                long sum = k * (long) c[2];
                max = Math.max(max, sum);
            }
            if (k >= window && k <= window + len) { // fill to the right
                long rSum = curr + (k - window) * (long) c[2];
                max = Math.max(max, rSum);
            }
            // swallow
            curr = curr + len * (long) c[2];
            window += len;
            while (start < i && window > k) {
                len = coins[start][1] - coins[start][0] + 1;
                long old = len * (long) coins[start][2];
                start++;
                window = c[1] + 1 - coins[start][0];
                curr = curr - old;
            }
            if (window <= k) {
                max = Math.max(curr, max);
            }
            if (start < i && window == k) { // no need to keep
                len = coins[start][1] - coins[start][0] + 1;
                long old = len * (long) coins[start][2];
                start++;
                window = c[1] + 1 - coins[start][0];
                curr = curr - old;
            } else if (window < k && start != 0 && start <= i) { // can extend back
                len = coins[start][0] - coins[start - 1][1] - 1;
                if (window + len < k) {
                    long lSum = curr + (k - window - len) * (long) coins[start - 1][2];
                    max = Math.max(max, lSum);
                }
                // and if we swallow left
                window = c[0] - coins[start - 1][0];
                len = c[1] - c[0] + 1;
                if (k >= window && k <= window + len) {
                    long rSum = curr - (len - k + window) * (long) c[2] + (coins[start - 1][1] - coins[start - 1][0] + 1) * (long) coins[start - 1][2];
                    max = Math.max(max, rSum);
                }
            }
        }
        return max;
    }
}
```
['Sliding Window', 'Line Sweep', 'Sorting', 'Java']