step multiple bags when sliding window
IntuitionSliding window with 2 pointers (segment on the left and segment on th right).Step reasonable number of bags instead of step for every single bag, becau
# Intuition

Sliding window with 2 pointers (segment on the left and segment on th right).

Step reasonable number of bags instead of step for every single bag, because the problem mentioned many many bags.

# Approach

Replace `std::vector<std::vector<int>> coins` by `std::vector<std::tuple<int, int, int>> vSegment` then sort `vSegment`.

Calculate total coins in the first applicable k-consecutive bags.

Slide the window (k-consecutive bags) from left to right. Step to next bag of interest rather than step at every bag in a segment. The next bag of interest is usually the end of the current segment or the first bag of next segment. While we consider the left-most bag and the right-most bag, step is usually the minimum of "next left bag of interest" and "next right bag of interest". My expression of the minimum may evaluate to zero value, therefore step is `1` when the minimum expression evaluates to zero.

When slide the window,
1. exclude coins in bags on the left
2. include coins in bags on the right
3. update the maximum coins so far

Return the maximum coins as the answer.

# 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 []

#define DBG (0)

class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k)
    {
        std::vector<std::tuple<int, int, int>> vSegment; vSegment.reserve(coins.size());
        for (std::vector<int> const &c : coins)
        {
            vSegment.emplace_back(c[0], c[1], c[2]);
        }
        // 1. sort the segments
        std::sort(vSegment.begin(), vSegment.end());

        auto itSegmentL = vSegment.begin();
        auto itSegmentR = vSegment.begin();
        auto const itSegmentEnd = vSegment.end();
        int nL = std::get<0>(*itSegmentL);
        int nR = nL + k - 1;
        long long llCoin_running = 0ll;
        // 2. calculate coins in the first k-consecutive bags of interest
        for (; itSegmentR != itSegmentEnd && std::get<1>(*itSegmentR) <= nR; ++itSegmentR)
        {
            int64_t const nCount = std::get<1>(*itSegmentR) + 1 - std::get<0>(*itSegmentR);

            llCoin_running += nCount * std::get<2>(*itSegmentR);
        }
        if (itSegmentR != itSegmentEnd && std::get<0>(*itSegmentR) <= nR)
        {
            int64_t const nCount = nR + 1 - std::get<0>(*itSegmentR);

            llCoin_running += nCount * std::get<2>(*itSegmentR);
        }
        long long llCoin_max = llCoin_running;
        #if DBG
        std::cout << '[' << nL << ',' << nR << ']' << std::endl;
        std::cout << "\tMax Coin: " << llCoin_max << std::endl;
        #endif

        // 3. slide k-consecutive bags from left to right
        while (itSegmentR != itSegmentEnd && nR < std::get<1>(vSegment.back()))
        {
            int const nL0 = nL;
            int const nR0 = nR;

            int const nDelta = std::max(1, std::min
            (
                (nL0 < std::get<0>(*itSegmentL) ? std::get<0>(*itSegmentL) : std::get<1>(*itSegmentL) + 1) - nL0,
                (nR0 < std::get<0>(*itSegmentR) ? std::get<0>(*itSegmentR) : std::get<1>(*itSegmentR)) - nR0
            ));
            int const nL1 = nL0 + nDelta;
            int const nR1 = nR0 + nDelta;

            #if DBG
            std::cout << '[' << nL1 << ',' << nR1 << ']' << std::endl;
            #endif

            if (std::get<0>(*itSegmentL) <= nL0 && nL0 <= std::get<1>(*itSegmentL))
            {
                int64_t const nCount = std::min(std::get<1>(*itSegmentL) + 1, nL1) - nL0;

                #if DBG
                std::cout << "\tExclude " << nCount << " bag(s) from segment {" << std::get<0>(*itSegmentL) << ',' << std::get<1>(*itSegmentL) << ',' << std::get<2>(*itSegmentL) << '}' << std::endl;
                #endif

                llCoin_running -= nCount * std::get<2>(*itSegmentL);
            }
            if (std::get<1>(*itSegmentL) < nL1)
            {
                if (++itSegmentL != itSegmentEnd)
                {
                    if (std::get<0>(*itSegmentL) < nL1)
                    {
                        int64_t const nCount = nL1 - std::get<0>(*itSegmentL);

                        #if DBG
                        std::cout << "\tExclude " << nCount << " bag(s) from segment {" << std::get<0>(*itSegmentL) << ',' << std::get<1>(*itSegmentL) << ',' << std::get<2>(*itSegmentL) << '}' << std::endl;
                        #endif

                        llCoin_running -= nCount * std::get<2>(*itSegmentL);
                    }
                }
            }

            if ((std::get<0>(*itSegmentR) <= nR0 && nR0 <= std::get<1>(*itSegmentR)) ||
                (std::get<0>(*itSegmentR) <= nR1 && nR1 <= std::get<1>(*itSegmentR)))
            {
                int64_t const nCount = std::min(std::get<1>(*itSegmentR), nR1) - std::max(std::get<0>(*itSegmentR) - 1, nR0);

                #if DBG
                std::cout << "\tInclude " << nCount << " bag(s) from segment {" << std::get<0>(*itSegmentR) << ',' << std::get<1>(*itSegmentR) << ',' << std::get<2>(*itSegmentR) << '}' << std::endl;
                #endif
                
                llCoin_running += nCount * std::get<2>(*itSegmentR);
            }
            if (std::get<1>(*itSegmentR) < nR1)
            {
                if (++itSegmentR != itSegmentEnd)
                {
                    if (std::get<0>(*itSegmentR) <= nR1)
                    {
                        int64_t const nCount = nR1 - std::get<0>(*itSegmentR) + 1;

                        #if DBG
                        std::cout << "\tInclude " << nCount << " bag(s) from segment {" << std::get<0>(*itSegmentR) << ',' << std::get<1>(*itSegmentR) << ',' << std::get<2>(*itSegmentR) << '}' << std::endl;
                        #endif

                        llCoin_running += nCount * std::get<2>(*itSegmentR);
                    }
                }
            }

            nL = nL1;
            nR = nR1;
            llCoin_max = std::max(llCoin_max, llCoin_running);
            #if DBG
            std::cout << "\tMax Coin: " << llCoin_max << std::endl;
            #endif
        }
        return llCoin_max;
    }
};

static auto _______ = []() {
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return 0;
}();
```
['Two Pointers', 'Sliding Window', 'C++']