Easy Binary Search New Approach
Intuitionwe have given to select k consecutive elements and since for 1e9 we cannot traverse on every index and apply sliding window. So we need to check that f
# Intuition
we have given to select k consecutive elements and since for 1e9 we cannot traverse on every index and apply sliding window. So we need to check that for a particular index given in coins array what is the last element and where it lies.So, directy traverse all the ranges given and find the last element where it lies. Use Binary search.


# Approach
There are two main loops first is that take the starting element and second is to take end element and in them.
Ok SO traversing each and every element and then check that what is the index of element which is k coordinate away basically i want to find that in which range that element lies then consider the coins between index and current index basically we just get the index of range in which it lying now for calculating the actual coins we just add the coins in between these ranges and also + coins left in last index.
suppose 1 2 3 4 is the first range coins(10) and 7 8 9 is the second range coins(4) and 11 12 13 is third range coins(8) so traversing the first element of all range and suppose k=4 now we just go on every range and just check that where the next kth element lie upto.
so here we get index as 0 since all four element lies in first range so add it in ans now go on second range 7 8 9 for 7 just check next indexwhere it lies so for k=4 it would be 10 but having no index so it would also lie in this range so just by doing so we can find the total coins lying in k elements by using prefix sum which we will store initially.so by using prefix sum we can find the total eleemnts lying in between two range.

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

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

# Code
```cpp []
class Solution {
public:

    int binarySearch(const vector<int>& BS, int target,int curr) {
        int low = 0, high = BS.size() - 1, ans = curr;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (BS[mid] <= target) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans; // Return the index of the largest element <= target
    }
    int findGreaterEqualIndex(const vector<int>& BS, int target,int curr) {
    int low = 0, high = BS.size() - 1, ans = curr;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (BS[mid] >= target) {  // Check for greater than or equal to
            ans = mid;           // Update the answer
            high = mid - 1;      // Search in the left half
        } else {
            low = mid + 1;       // Search in the right half
        }
    }
    return ans; // Return the index of the smallest element >= target, or -1 if not found
}


    long long maximumCoins(vector<vector<int>>& coins, int k) {
        // Sort based on the starting index
        sort(coins.begin(), coins.end());
        int n = coins.size();
        long long maxAns = 0;

        // Precompute the start indices and total coins for ranges
        vector<int> BS(n, 0);
        vector<long long> totalCoinsInRange(n, 0);
        for (int i = 0; i < n; i++) {
            BS[i] = coins[i][0];
        }

        long long tillNow = 0;
        for (int i = 0; i < n; i++) {
            totalCoinsInRange[i] = tillNow;
            tillNow +=(long long)(coins[i][1] - coins[i][0] + 1) * coins[i][2];
        }

        // Check maximum coins by taking `i` as the starting index
        for (int i = 0; i < n; i++) {
            if (BS[i] + k - 1 > coins[n - 1][1]) break; // Early exit if the range exceeds the target
            int index = binarySearch(BS, BS[i] + k - 1,i);
            
            int diff = k - (BS[index] - BS[i]);
            long long coinsCollected = totalCoinsInRange[index] - totalCoinsInRange[i];
            coinsCollected += (long long)(min(diff,coins[index][1]-coins[index][0]+1) *(long long) coins[index][2]);
            maxAns = max(maxAns, coinsCollected);
            cout<<index<<" "<<maxAns<<endl;
        }

        // Check maximum coins by taking `i` as the ending index
        vector<int>BS2(BS.size(),0);
        for(int i=0;i<coins.size();i++){
            BS2[i]=coins[i][1];
        }
        vector<long long> totalCoinsInRange2(n, 0);
         tillNow = 0;
        for (int i = 0; i < n; i++) {
           
            tillNow +=(long long)(coins[i][1] - coins[i][0] + 1) * coins[i][2];
             totalCoinsInRange2[i] = tillNow;
        }
        for (int i = n - 1; i >= 0; i--) {
             // Early exit if the range exceeds the target
            int index = findGreaterEqualIndex(BS2, BS2[i] - k + 1,i);
          
            int diff = k - (BS2[i] - BS2[index]);
            long long coinsCollected = totalCoinsInRange2[i] - totalCoinsInRange2[index];
            cout<<coinsCollected<<endl;
            coinsCollected += min((long long)diff,(long long)coins[index][1]-coins[index][0]+1) * coins[index][2];
            
            maxAns = max(maxAns, coinsCollected);
            cout<<index<<" "<<maxAns<<endl;
        }

        return maxAns;
    }
};

```
['Binary Search', 'Sliding Window', 'C++']