Untitled
unknown
python
2 years ago
1.0 kB
3
Indexable
Never
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