JavaScript O(nlgn): Just test left and right edges of ranges, with binary search
IntuitionThe best outcome can be obtained with the collection starting from some range's left edge, or ending to some range's right edge.Approach
Build two pref
# Intuition
The best outcome can be obtained with the collection starting from some range's left edge, or ending to some range's right edge.
# Approach
1. Build two prefix sums.
2. Go from left to right, trying to start the collection from some range's left edge, and see how far it reaches using binary search.
3. Go from right to left, trying to end the collection to some range's right edge, and see how far it reaches using binary search.
4. The result is the maximum outcome.
# Complexity
- Time complexity:
O(nlgn)
- Space complexity:
O(n)
# Code
```javascript []
/**
 * @param {number[][]} coins
 * @param {number} k
 * @return {number}
 */
var maximumCoins = function(coins, k) {
    k--
    coins.sort((A, B) => A[0] - B[0])
    const len = coins.length

    const sumFL = new Array(len), sumFR = new Array(1 + len)
    sumFL[-1] = sumFR[len] = 0
    for (let i = 0; i < len; i++) {
        const range = coins[i]
        const [l, r, c] = range
        const outcome = (1 + r - l) * c
        sumFL[i] = outcome + sumFL[i - 1]
        range.push(outcome)
    }
    for (let i = len - 1; i > -1; i--) {
        const range = coins[i]
        sumFR[i] = range[3] + sumFR[i + 1]
    }


    let result = 0
    const minLeft = coins[0][0], maxRight = coins.at(-1)[1]
    for (let i = 0; i < len; i++) {
        const range = coins[i]
        const edgeLeft = range[0]
        let low = i, high = len - 1

        if (maxRight - edgeLeft <= k) {
            const outcome = sumFL[high] - sumFL[i - 1]
            result = Math.max(result, outcome)
            break
        }
        // find latest low where
        // coins[low][0] - edgeLeft <= k
        while (low < high) {
            const mid = Math.ceil((low + high) / 2)
            if (coins[mid][0] - edgeLeft <= k)
                low = mid
            else
                high = mid - 1
        }
        const other = coins[low]
        const [otherLeft, otherRight, otherCount] = other
        const edgeRight = Math.min(otherRight, edgeLeft + k)
        const lastOutcome = (1 + edgeRight - otherLeft) * otherCount
        const outcome = sumFL[low - 1] - sumFL[i - 1] + lastOutcome
        result = Math.max(result, outcome)
    }
    for (let i = len - 1; i > -1; i--) {
        const range = coins[i]
        const edgeRight = range[1]
        let low = 0, high = i
        if (edgeRight - minLeft <= k) {
            const outcome = sumFR[low] - sumFR[i + 1]
            result = Math.max(result, outcome)
            break
        }

        // find earliest high where
        // edgeRight - coins[high][1] <= k
        while (low < high) {
            const mid = Math.floor((low + high) / 2)
            if (edgeRight - coins[mid][1] <= k)
                high = mid
            else
                low = mid + 1
        }
        const other = coins[high]
        const [otherLeft, otherRight, otherCount] = other
        const edgeLeft = Math.max(otherLeft, edgeRight - k)
        const lastOutcome = (1 + otherRight - edgeLeft) * otherCount
        const outcome = sumFR[high + 1] - sumFR[i + 1] + lastOutcome
        result = Math.max(result, outcome)
    }


    return result
};
```
['JavaScript']