Java | 129 ms | Beats 100 % | Binary Search + Prefix Sum
IntuitionBinary Search + Prefix SumApproachRan two for loops to calculate the sum of coins.
First For loop assumes the ith index to be taken completely and to b
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Binary Search + Prefix Sum

# Approach
<!-- Describe your approach to solving the problem. -->
Ran two for loops to calculate the sum of coins.
First For loop assumes the ith index to be taken completely and to be the first of the sequence. Hence, starts looking to the right of ith index in coins array.
Second For loop assumes the ith index to be taken completely and to be the last of the sequence. Hence, starts looking to the left of ith index in coins array.

Binary Search is used to get upper and lower bounds until where the full coin range is to be considered from the coins array.
To calculate complete range coin sums, Prefix Sum array is used.

And then for the remaining part (partial range), sum is calculated by multiplying the coin value to the number of elements in the partial range.

Now sum up the Complete range sum and the partial range sum.

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

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


# Code
```java []
class Solution {
    public int getUB(int[][] coins, int end, long t){
        int n = coins.length;
        int ans = -1;
        int low = 0;
        int high = end;
        while(low <= high){
            int mid = (low + high) / 2;
            if(t < coins[mid][0]){
                ans = mid;
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }
        }
        return ans;
    }
    public int getLB(int[][] coins, int start, long t){
        int n = coins.length;
        int ans = -1;
        int low = start;
        int high = n - 1;
        while(low <= high){
            int mid = (low + high) / 2;
            if(coins[mid][1] < t){
                ans = mid;
                low = mid + 1;
            }
            else{
                high = mid - 1;
            }
        }
        return ans;
    }
    public long maximumCoins(int[][] coins, int k) {
        Arrays.sort(coins, (a, b) -> a[0] - b[0]);
        long ans = 0;
        int n = coins.length;
        long[] prefSum = new long[n + 1];
        for(int i = 0; i<n; i++){
            prefSum[i + 1] = prefSum[i] + 1L*coins[i][2]*(coins[i][1] - coins[i][0] + 1);
        }
        //for loop assuming that ith index is the first complete coin range taken in the sequence
        // looks to right of ith index to see which all coin ranges need to be taken partial or complete
        for(int i = 0; i<n; i++){
            int[] curr = coins[i];
            int start = curr[0];
            int end = curr[1];
            int currCoins = curr[2];

            int lb = getLB(coins, i, start + k - 1);
            long currMax = 0;
            if(lb == -1){
                currMax = 1L*currCoins*k; // ith partial range taken
            }
            else{
                currMax = prefSum[lb + 1] - prefSum[i]; // complete range taken from ith to lb-th in coins array
            }
            if(lb != -1 && lb + 1 < n && coins[lb + 1][0] <= start + k - 1){ // adding the last partial range at lb + 1
                currMax += 1L*coins[lb + 1][2]*(start + k - 1 - coins[lb + 1][0] + 1);
            }
            ans = Math.max(currMax, ans);
        }
        // for loop assuming that ith index is the last complete coin range taken in the sequence
        // looks to left of ith index to see which all coin ranges need to be taken partial or complete
        for(int i = 0; i<n; i++){
            int[] curr = coins[i];
            int start = curr[0];
            int end = curr[1];
            int currCoins = curr[2];

            int ub = getUB(coins, i, end - k + 1);
            long currMax = 0;
            if(ub == -1){
                currMax = 1L*currCoins*k; // ith partial range taken
            }
            else{
                currMax = prefSum[i + 1] - prefSum[ub]; // complete range taken from ub-th coin range to ith coin range
            }
            if(ub - 1 >= 0 && coins[ub - 1][1] >= end - k + 1){ // adding the partial coin range at (ub - 1)th index in coins array
                currMax += 1L*coins[ub - 1][2]*(coins[ub - 1][1] - (end - k + 1) + 1);
            }
            ans = Math.max(ans, currMax);
        }
        return ans;
    }
}
```
['Binary Search', 'Java']