Untitled

class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        ends = []
        tiles.sort(key=lambda x: x[1])
        prefix_sum = [0]
        for l, r in tiles:
            ends.append(r)
            prefix_sum.append(r - l + 1 + prefix_sum[-1])
        res = 0
        def binary_search(nums, val):
            l, r = 0, len(nums) - 1
            while l < r:
                mid = (l + r + 1) // 2
                if nums[mid] > val:
                    r = mid - 1
                else:
                    l = mid
            return l
        for i, tile in enumerate(tiles):
            l, r = tile
            end = l + carpetLen - 1
            r_bound = binary_search(ends, end)
            cur_res = prefix_sum[r_bound+1] - prefix_sum[i]
            # print(ends, end, r_bound)
            if r_bound + 1 < len(tiles) and tiles[r_bound+1][0] < end:
                cur_res += end - tiles[r_bound+1][0] + 1
            res = max(res, cur_res)
        return res