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