en/lc/3413/

[giscus[bot]]

en/lc/3413/

LeetCode solutions in any programming language

https://leetcode.doocs.org/en/lc/3413/

[AmolGode]

Approach: Sort ranges + Sliding Window.

Add fully covered ranges to cur_sum; remove ranges outside the window.

Subtract the uncovered part of the left range to calculate the actual sum.

REV is IMP: run on [-r, -l, value] to check partial coverage on the opposite side.

class Solution:
    def maximumCoinsHelper(self, coins: List[List[int]], k: int) -> int:
        n = len(coins)

        coins.sort() # <---- VIMP

        START = 0
        END = 1
        VALUE = 2


        left = 0
        cur_sum = 0
        max_res = 0

        for right in range(n):
            r_start = coins[right][START]
            r_end = coins[right][END]
            r_val = coins[right][VALUE]

            r_win_size = (r_end-r_start) + 1 
            r_range_sum = r_win_size*r_val

            cur_sum += r_range_sum # 3 + 6 ..

            win_start_pos = r_end-k+1 # [0,1,2,3,4,5], ex: r_st=4 k=3 -> 4-3-1 => 2

            # Remove out of range ranges
            while coins[left][END] < win_start_pos:
                l_start = coins[left][START]
                l_end = coins[left][END]
                l_val = coins[left][VALUE]

                l_win_size = (l_end-l_start) + 1 
                l_range_sum = l_win_size*l_val

                cur_sum -= l_range_sum
                left += 1
            

            # Partially covered ranges case
            l_start = coins[left][START]
            l_end = coins[left][END]
            l_val = coins[left][VALUE]

            uncovered_l_range_sum = 0
            if l_start < win_start_pos:
                l_uncovered_win_size = (win_start_pos-l_start)
                uncovered_l_range_sum = l_uncovered_win_size*l_val
            
            max_res = max(max_res, cur_sum-uncovered_l_range_sum)
        
        return max_res
    


    # extended aproach of https://leetcode.com/problems/maximum-white-tiles-covered-by-a-carpet/
    def maximumCoins(self, coins: List[List[int]], k: int) -> int:
        reversed_coins = [(-r, -l, v) for l, r, v in coins]

        # REV is IMP: Our window logic handles RIGHT full + LEFT partial coverage.
        # The best window may also have LEFT full + RIGHT partial coverage.
        # Reverse ranges [-r, -l, value] to check the opposite direction.
        # Example: [5, 6, 4] -> [-6, -5, 4]
        # Range size = -5 - (-6) + 1 = -5 + 6 + 1 = 2
        # This lets us reuse the same sliding-window logic for both cases.

        return max(
            self.maximumCoinsHelper(coins, k),
            self.maximumCoinsHelper(reversed_coins, k)
        )