Maximum Coins Collection from Intervals with Fixed Subarray Size
IntuitionTo solve the problem of maximizing the number of coins collected from given intervals with a fixed size k, we can leverage sorting, prefix sums, and bi
### Intuition  
<!-- Describe your first thoughts on how to solve this problem. -->  
To solve the problem of maximizing the number of coins collected from given intervals with a fixed size `k`, we can leverage sorting, prefix sums, and binary search. Sorting helps structure the intervals in a logical order, prefix sums allow efficient calculation of cumulative sums, and binary search helps identify relevant intervals for computation quickly.  

### Approach  
<!-- Describe your approach to solving the problem. -->  
1. **Sort Intervals**:  
   Sort the intervals based on their starting points to ensure overlapping intervals are grouped logically.  

2. **Prefix Sum Array**:  
   Compute a prefix sum array where each element holds the cumulative sum of coins up to that interval.  

3. **Calculate Maximum Coins from Start Points**:  
   - For each interval, calculate the start (`start`) and end (`end = start + k - 1`) of the subarray.  
   - Use `upper_bound` to find the index of the last interval whose start point lies within the range `[start, end]`.  
   - Use the prefix sum array to calculate the contribution of fully covered intervals.  
   - Add the contribution of the partially overlapping interval.  

4. **Calculate Maximum Coins from End Points**:  
   - Repeat the same process but start from the end of each interval (`end`) and calculate the start (`start = end - k + 1`) of the subarray.  
   - Use `lower_bound` to find the first interval whose end point lies within the range `[start, end]`.  

5. **Update Maximum**:  
   Keep track of the maximum coins collected during both iterations.  

---

### Complexity  
- **Time complexity**:  
  - Sorting the intervals takes $$O(n \log n)$$.  
  - Calculating prefix sums and performing binary searches for each interval takes $$O(n \log n)$$.  
  Overall time complexity is $$O(n \log n)$$.  

- **Space complexity**:  
  - Prefix sum array and auxiliary arrays for starts and ends take $$O(n)$$.  
  Space complexity is $$O(n)$$.  

---

### Code  
```cpp
class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        long long n = (coins.size());
        long long maxi = -1e9;

        // Creating the prefix array
        vector<long long> pref(n + 1, 0);
        vector<long long> start_arr;
        vector<long long> end_arr;
        long long sum = 0;

        // Sort intervals by starting points
        sort(coins.begin(), coins.end());

        for (long long i = 0; i < n; i++) {
            pref[i] = sum;
            sum += coins[i][2] * 1LL * (coins[i][1] - coins[i][0] + 1);
        }
        pref[n] = sum;

        for (long long i = 0; i < n; i++) {
            start_arr.push_back(coins[i][0]);
            end_arr.push_back(coins[i][1]);
        }

        // Starting from each start point
        for (long long i = 0; i < n; i++) {
            long long ans = 0;
            long long start = coins[i][0];
            long long end = start + k - 1;

            auto ind = upper_bound(start_arr.begin(), start_arr.end(), end) - start_arr.begin() - 1;
            ans += (pref[ind] - pref[i]);
            ans += (min(coins[ind][1], int(end)) - coins[ind][0] + 1) * 1LL * coins[ind][2];
            maxi = max(maxi, ans);
        }

        // Starting from each end point
        for (long long i = n - 1; i >= 0; i--) {
            long long ans = 0;
            long long start = coins[i][1];
            long long end = start - k + 1;

            auto ind = lower_bound(end_arr.begin(), end_arr.end(), end) - end_arr.begin();
            ans += pref[i + 1] - pref[ind + 1];
            ans += (coins[ind][1] + 1 - max(coins[ind][0], int(end))) * 1LL * coins[ind][2];
            maxi = max(maxi, ans);
        }

        return maxi;
    }
};
```  
['C++']