给你一个二维整数数组 tiles ,其中 tiles[i] = [li, ri]
,表示所有在 li <= j <= ri
之间的每个瓷砖位置 j 都被涂成了白色。
同时给你一个整数 carpetLen
,表示可以放在 任何位置 的一块毯子。
请你返回使用这块毯子,最多 可以盖住多少块瓷砖。
示例 1:
输入:tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]],
carpetLen = 10
输出:9
解释:将毯子从瓷砖 10 开始放置。
总共覆盖 9 块瓷砖,所以返回 9 。
注意可能有其他方案也可以覆盖 9 块瓷砖。
可以看出,瓷砖无法覆盖超过 9 块瓷砖。
示例 2:
输入: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 互相 不会重叠 。
来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
i
,在 [i, n-1]
中二分查找 最后一个区间 j
(titles[j][0] <= titles[i][0]+carpetLen
), j
能够被盖住部分或者全部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
824 ms 31 MB Python3