LeetCode 2271. 毯子覆盖的最多白色砖块数（前缀和+二分查找）

输入：tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]],
 carpetLen = 10
输出：9
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 9 块瓷砖，所以返回 9 。
注意可能有其他方案也可以覆盖 9 块瓷砖。
可以看出，瓷砖无法覆盖超过 9 块瓷砖。

输入：tiles = [[10,11],[1,1]], carpetLen = 2
输出：2
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 2 块瓷砖，所以我们返回 2 。
 
提示：
1 <= tiles.length <= 5 * 10^4
tiles[i].length == 2
1 <= li <= ri <= 10^9
1 <= carpetLen <= 10^9
tiles 互相 不会重叠 。

class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        n = len(tiles)
        prevsum = [0]*n
        tiles.sort(key=lambda x : x[0])
        for i in range(n):
            prevsum[i] = (prevsum[i-1] if i>0 else 0) + tiles[i][1]-tiles[i][0]+1
        ans = 0
        for i in range(n):
            val = tiles[i][0] + carpetLen - 1
            if val <= tiles[i][1]:
                return carpetLen
            l, r, j = i, n-1, -1  # 二分查找 左端点<= val 的最后一个区间
            while l <= r:
                mid = (l+r)//2
                if tiles[mid][0] > val:
                    r = mid-1
                else:
                    if mid==n-1 or tiles[mid+1][0] > val:
                        j = mid
                        break
                    else:
                        l = mid+1
            cover = prevsum[j-1] - (0 if i==0 else prevsum[i-1]) + min(val, tiles[j][1]) - tiles[j][0] + 1
            ans = max(ans, cover)
        return ans