evulate the interval through two passes
IntuitionWe should evaluate the windows interval size k through two passes:
interval start with l_i
interval end with r_i
ApproachComplexity
Time complexity:

S
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We should evaluate the windows interval size k through two passes:
1. interval start with l_i
2. interval end with r_i
# Approach
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```python3 []
class Solution:
    def maximumCoins(self, coins: List[List[int]], k: int) -> int:
        # Sort the segments based on starting positions
        coins.sort()
        
        n = len(coins)
        
        # # Extract separate lists for binary search
        starts = [seg[0] for seg in coins]
        ends = [seg[1] for seg in coins]
        # coin_vals = [seg[2] for seg in coins]
        
        # Compute prefix sums
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            li, ri, ci = coins[i]
            prefix_sum[i + 1] = prefix_sum[i] + ci * (ri - li + 1)
        
        # Helper function to find the first segment with ri >= x
        def find_left(x):
            return bisect.bisect_left(ends, x)
        
        # Helper function to find the last segment with li <= y
        def find_right(y):
            return bisect.bisect_right(starts, y) - 1
        
        # Helper function to calculate total coins in window [x, y]
        def calculate_sum(x, y):
            if x > y:
                return 0
            l = find_left(x)
            r = find_right(y)
            if l > r:
                return 0
            total = prefix_sum[r + 1] - prefix_sum[l]
            
            # Adjust for partial overlap on the left
            seg_l_start, seg_l_end, seg_l_ci = coins[l]
            if seg_l_start < x:
                overlap = seg_l_end - x + 1
                if overlap > 0:
                    total -= seg_l_ci * (seg_l_end - seg_l_start + 1)
                    total += seg_l_ci * overlap
            
            # Adjust for partial overlap on the right
            seg_r_start, seg_r_end, seg_r_ci = coins[r]
            if seg_r_end > y:
                overlap = y - seg_r_start + 1
                if overlap > 0:
                    total -= seg_r_ci * (seg_r_end - seg_r_start + 1)
                    total += seg_r_ci * overlap
            
            return total
        
        max_total = 0
        
        # Iterate through each segment and consider both window start and end
        for seg in coins:
            seg_start, seg_end, _ = seg
            
            # 1. Consider seg_start as window start
            window_start = seg_start
            window_end = window_start + k - 1
            total = calculate_sum(window_start, window_end)
            if total > max_total:
                max_total = total
            
            # 2. Consider seg_end as window end
            window_end = seg_end
            window_start = window_end - k + 1
            if window_start < 1:
                window_start = 1
            total = calculate_sum(window_start, window_end)
            if total > max_total:
                max_total = total
        
        return max_total
            


        
```
['Python3']