Sorting + PrefixSum + Binary Search - O(nlogn)
IntuitionThe key observation is that the interval we are looking for will always either start with one of the intervals containing coins or end at one of these
# Intuition
The key observation is that the interval we are looking for will always either start with one of the intervals containing coins or end at one of these intervals. Based on this, we can handle the problem in two cases:

1. Starting with a Coin Interval:
For each coin-containing interval, assume it as the starting point of the 
𝑘
k-length interval. Then, use binary search to find the end of this interval.
2. Ending with a Coin Interval:
For each coin-containing interval, assume it as the ending point of the 
𝑘
k-length interval. Use binary search to find the start of this interval.
In both cases, if the end (or start) falls in the middle of a coin-containing interval, we handle the partial overlap accordingly. Once the start (or end) is determined, we use the prefix sum array to efficiently calculate the total number of coins in the selected interval.
# Approach
1. Sorting and Prefix Sum:
Sort the segments based on their start positions. Create a prefix sum array to quickly calculate the total number of coins in any subarray (interval).

2. Two Loops for Both Cases:

    - First Loop (Start with Coin Interval):
    For each interval containing coins, treat it as the starting point of the 𝑘-length interval. Use binary search (lower_bound) to find where the interval should end.

    - Second Loop (End with Coin Interval):
    For each interval containing coins, treat it as the end of the  k-length interval. Again, use binary search to find where the interval should start.

3. Handling Partial Overlap:
If the start or end of the interval lies within a coin-containing interval, handle the partial overlap by calculating the contribution of coins in the overlapping portion.

4. Update Maximum Coins:
Track the maximum coins obtained from both scenarios.
# Complexity
- Time complexity:
Sorting the coins takes $$O(nlogn)$$. For each of the two loops, we perform a binary search which takes $$O(logn)$$, leading to an overall time complexity of $$O(nlogn)$$.
- Space complexity:
The space complexity is $$O(n)$$ due to the prefix sum and auxiliary arrays


# Code
```cpp []
class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        //sort the array and store starts and ends of interval seperately to make binary search easier
        int n = coins.size();
        sort(coins.begin(), coins.end()); 
        vector<long long> prefix(coins.size()+1, 0); 
        vector<int> starts(n), ends(n);

        //precalculate the prefix sum for calculation of score
        for(int i=0; i<n; i++){
            starts[i] = coins[i][0]; 
            ends[i] = coins[i][1]; 
            prefix[i+1] = prefix[i] + 1LL*(coins[i][1]-coins[i][0]+1)*coins[i][2];
        }

        long long ans = 0; //final_score

        // First loop: Treat each coin-containing interval as the start of the k-length interval
        for(int i=0; i<n; i++){
            long long curr = 0; //score for this iteration
            int s = coins[i][0], target = s + k - 1; 
            int j = lower_bound(ends.begin(), ends.end(), target)- ends.begin();
            curr += 1LL*(prefix[j] - prefix[i]); 
            if(j<n) curr += 1LL*max(0, target - coins[j][0] + 1)*coins[j][2]; //handle partial overlap
            ans = max(curr, ans); 
        }

        // Second loop: Treat each coin-containing interval as the end of the k-length interval
        for(int i=0; i<n; i++){
            long long curr = 0;
            int s = coins[i][1]; 
            int target = s - k + 1; 
            int j = lower_bound(starts.begin(), starts.end(), target) - starts.begin();
            curr += 1LL*(prefix[i+1] - prefix[j]); 
            if(j>0) curr += 1LL*max(0,  coins[j-1][1] - target + 1)*coins[j-1][2]; //handle partial overlap
            ans = max(curr, ans); 
        }
        
        return ans;
    }
};
```
['C++']