O(n*log(n)) | 2 Pointers | Code Reusebility
IntuitionThe solution will contain atleast "one segment where we take all the bags(at most k) for it"ApproachSort and do 2 pointersComplexity
Time complexity:
O
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The solution will contain atleast "one segment where we take all the bags(at most k) for it"

# Approach
<!-- Describe your approach to solving the problem. -->
Sort and do 2 pointers

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

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

# Code
```cpp []
class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        /*
            The solution will contain atleast "one segment where we take all the bags(at most k) for it"
        */
        
        auto cmp = [&](const vector<int> &a, const vector<int>&b) {
            return a[0] < b[0];
        };
        
        sort (coins.begin(), coins.end(), cmp);
        
        
        long long  mx = 0;
        int n = coins.size();
        
        auto solve = [&]() {
            int l = 0, r = 0;
            long long have = 0;
            while (l<n) {
                while (r < n && abs(coins[l][0] - coins[r][0]) + 1 <= k) {
                    long long took = min(abs(coins[r][1] - coins[r][0])+1, k - (abs(coins[l][0] - coins[r][0])));
                    mx = max(mx, have + took * coins[r][2]);
                    if (abs(coins[r][1] - coins[l][0])+1 > k) {
                        break;
                    }
                    have += took * coins[r][2];
                    r += 1;
                }
                if (r > l) {
                    have -= 1ll * (abs(coins[l][0] - coins[l][1]) + 1) * coins[l][2];
                    assert (have >= 0);
                } else {
                    r = l+1;
                    have = 0;
                }
                l += 1;
            }
        };
        
        solve(); // This will take care when some next one is taken partial
        
        reverse(coins.begin(), coins.end());
        for (auto &v: coins){
            swap(v[0], v[1]);
        }
        
        
        solve(); // This will take care when some previous one is taken partial
        
        return mx;  
    }
};
```




```Rust []
impl Solution {
    pub fn maximum_coins(coins: Vec<Vec<i32>>, k: i32) -> i64 {
        /*
            The solution will contain at least "one segment where we take all the bags (at most k) for it."
        */
        
        let mut coins = coins;
        
        // Comparator for sorting by the start position (similar to cmp in C++).
        coins.sort_by(|a, b| a[0].cmp(&b[0]));
        
        let mut mx: i64 = 0;
        let n = coins.len();
        let k = k as i64; // Convert k to i64 for consistency with other operations.
        
        let solve = |coins: &Vec<Vec<i32>>, mx: &mut i64| {
            let mut l = 0;
            let mut r = 0;
            let mut have: i64 = 0;

            while l < n {
                while r < n && (coins[r][0] - coins[l][0]).abs() as i64 + 1 <= k {
                    let took = std::cmp::min(
                        (coins[r][1] - coins[r][0]).abs() as i64 + 1,
                        k - (coins[r][0] - coins[l][0]).abs() as i64,
                    );
                    *mx = std::cmp::max(*mx, have + took * coins[r][2] as i64);

                    if (coins[r][1] - coins[l][0]).abs() as i64 + 1 > k {
                        break;
                    }
                    have += took * coins[r][2] as i64;
                    r += 1;
                }

                if r > l {
                    have -= ((coins[l][1] - coins[l][0]).abs() as i64 + 1) * coins[l][2] as i64;
                    assert!(have >= 0);
                } else {
                    r = l + 1;
                    have = 0;
                }
                l += 1;
            }
        };

        // First solve pass
        solve(&coins, &mut mx);

        // Reverse the coins for the second pass
        coins.reverse();
        for coin in &mut coins {
            coin.swap(0, 1);
        }

        // Second solve pass
        solve(&coins, &mut mx);

        mx
    }
}
```

['C++']