431
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```javascript []
/**
 * @param {number[][]} coins
 * @param {number} k
 * @return {number}
 */
var maximumCoins = function(coins, k) {
    coins.sort((a, b) => a[0] - b[0]);
    
    let intervals = [];
    let prev_end = -1;
    for (let seg of coins) {
        let li = seg[0];
        let ri = seg[1];
        let ci = seg[2];
        if (prev_end !== -1 && li > prev_end + 1) {
            intervals.push([prev_end + 1, li - 1, 0]);
        }
        intervals.push([li, ri, ci]);
        prev_end = ri;
    }
    
    let parnoktils = coins.slice();
    
    let candidate_starts_set = new Set();
    for (let interval of intervals) {
        let start = interval[0];
        let end = interval[1];
        candidate_starts_set.add(start);
        let cand_start = end - k + 1;
        if (cand_start >= 1) {
            candidate_starts_set.add(cand_start);
        }
    }
    
    let candidates = [];
    for (let x of candidate_starts_set) {
        if (x <= intervals[intervals.length - 1][1]) {
            candidates.push(x);
        }
    }
    candidates.sort((a, b) => a - b);
    
    let n = intervals.length;
    let starts = Array(n);
    let ends = Array(n);
    let sums = Array(n);
    for (let i = 0; i < n; ++i) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
        sums[i] = intervals[i][2];
    }
    
    // Compute prefix sums of coins
    let prefix_sum = Array(n).fill(0);
    prefix_sum[0] = (ends[0] - starts[0] + 1) * sums[0];
    for (let i = 1; i < n; ++i) {
        prefix_sum[i] = prefix_sum[i - 1] + (ends[i] - starts[i] + 1) * sums[i];
    }
    
    let max_sum = 0;
    for (let x of candidates) {
        let window_end = x + k - 1;
        
        let l = binarySearch(ends, x);
        
        let r = binarySearch(starts, window_end, true) - 1;
        
        if (l > r || l >= n || r < 0) {
            continue;
        }
        
        let sum_coins = prefix_sum[r] - (l > 0 ? prefix_sum[l - 1] : 0);
        
        if (starts[l] < x) {
            let overlap = Math.min(ends[l], window_end) - x + 1;
            sum_coins -= (ends[l] - starts[l] + 1 - overlap) * sums[l];
        }
        
        if (ends[r] > window_end) {
            let overlap = window_end - starts[r] + 1;
            sum_coins -= (ends[r] - starts[r] + 1 - overlap) * sums[r];
        }
        
        max_sum = Math.max(max_sum, sum_coins);
    }
    
    return max_sum;
};


function binarySearch(arr, target, isUpper = false) {
    let low = 0;
    let high = arr.length;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] < target || (isUpper && arr[mid] <= target)) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}
```
['JavaScript']