Simplest Sliding Window after filling the gaps.
IntuitionThe problem can become much easier as soon as there is no gaps between intervals.
Once we have some continous intervals, we have to choose a segment of
# Intuition
The problem can become much easier as soon as there is no gaps between intervals. 
Once we have some continous intervals, we have to choose a segment of intervals such that it's lenght is K.

Now the observation is, every optimal segment selection will either start at some interval or end at some interval.
We can use simple sliding window `left to right` and `right to left` to get final optimal answer.

# Approach
- Sort the coins array to bring segments in sequence.
- Create another array storing the len and coins at each place.
- Make it continous by putting gaps with 0 coins at that place
- Apply sliding window left to right.
- Apply sliding window right to left.
- Return the final answer.


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

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

# Code
```cpp []
class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        sort(coins.begin(),coins.end());
        vector<vector<long long>> cc;
        cc.push_back({coins[0][1]-coins[0][0]+1,coins[0][2]});
        int last = coins[0][1];
        int n = coins.size();
        for(int i=1;i<n;i++)
        {
            int gapLen = coins[i][0] - last-1;
            cc.push_back({gapLen, 0});
            cc.push_back({coins[i][1]-coins[i][0]+1, coins[i][2]});
            last = coins[i][1];
        }
        // for(auto x:cc)
        // {
        //     cout<<x[0]<<" "<<x[1]<<endl;
        // }
        long long int ans = 0;
        n = cc.size();
        int i = 0, j=0;
        long long int tot=0, len=0;
        while(i<n)
        {
            len+=cc[i][0];
            tot+=cc[i][1]*cc[i][0];

            while(len>k)
            {
                len-=cc[j][0];
                tot-=cc[j][1]*cc[j][0];
                j++;
            }

            if(j-1>=0)
            {
                long long rem = k-len;
                ans = max(ans, tot+rem*cc[j-1][1]);
            }
            else
                ans = max(ans, tot);
            
            i++;
        }  

        j=n-1;
        i=n-1;
        tot = 0;
        len = 0;
        while(i>=0)
        {
            len+=cc[i][0];
            tot+=cc[i][1]*cc[i][0];

            while(len>k)
            {
                len-=cc[j][0];
                tot-=cc[j][1]*cc[j][0];
                j--;
            }

            if(j+1<n)
            {
                long long rem = k-len;
                ans = max(ans, tot+rem*cc[j+1][1]);
            }
            else
                ans = max(ans, tot);
            
            i--;
        }

        return ans;

    }
};
```
['Sliding Window', 'C++']