代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
给你一个二维整数数组 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 * 104tiles[i].length == 21 <= li <= ri <= 1091 <= carpetLen <= 109tiles 互相 不会重叠 。直觉上，毯子的左端点一定与某块瓷砖的左端点重合，这样才能使得毯子覆盖的瓷砖最多。
我们可以来简单证明一下。
如果毯子落在某块瓷砖的中间某个位置，将毯子右移一个，毯子覆盖的瓷砖数量可能减少，也可能不变，但不可能增加；将毯子左移一个，毯子覆盖的瓷砖数量可能不变，也可能增加，但不可能减少。
也就是说，将毯子左移至某块瓷砖的左端点，一定可以使得毯子覆盖的瓷砖数量最多。
因此，我们可以将所有瓷砖按照左端点从小到大排序，然后枚举每块瓷砖的左端点，计算出以该左端点为起点的毯子覆盖的瓷砖数量，取最大值即可。
为了计算以某块瓷砖的左端点为起点的毯子覆盖的瓷砖数量，我们可以使用滑动窗口的思想，维护一个右端点不断右移的窗口，窗口内的瓷砖数量即为毯子覆盖的瓷砖数量。
时间复杂度 $O(n\log n)$，其中 $n$ 为瓷砖的数量。
class Solution:
def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
tiles.sort()
n = len(tiles)
s = ans = j = 0
for i, (li, ri) in enumerate(tiles):
while j < n and tiles[j][1] - li + 1 <= carpetLen:
s += tiles[j][1] - tiles[j][0] + 1
j += 1
if j < n and li + carpetLen > tiles[j][0]:
ans = max(ans, s + li + carpetLen - tiles[j][0])
else:
ans = max(ans, s)
s -= ri - li + 1
return ans
class Solution {
public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
Arrays.sort(tiles, (a, b) -> a[0] - b[0]);
int n = tiles.length;
int s = 0, ans = 0;
for (int i = 0, j = 0; i < n; ++i) {
while (j < n && tiles[j][1] - tiles[i][0] + 1 <= carpetLen) {
s += tiles[j][1] - tiles[j][0] + 1;
++j;
}
if (j < n && tiles[i][0] + carpetLen > tiles[j][0]) {
ans = Math.max(ans, s + tiles[i][0] + carpetLen - tiles[j][0]);
} else {
ans = Math.max(ans, s);
}
s -= (tiles[i][1] - tiles[i][0] + 1);
}
return ans;
}
}
class Solution {
public:
int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
sort(tiles.begin(), tiles.end());
int s = 0, ans = 0, n = tiles.size();
for (int i = 0, j = 0; i < n; ++i) {
while (j < n && tiles[j][1] - tiles[i][0] + 1 <= carpetLen) {
s += tiles[j][1] - tiles[j][0] + 1;
++j;
}
if (j < n && tiles[i][0] + carpetLen > tiles[j][0]) {
ans = max(ans, s + tiles[i][0] + carpetLen - tiles[j][0]);
} else {
ans = max(ans, s);
}
s -= (tiles[i][1] - tiles[i][0] + 1);
}
return ans;
}
};
func maximumWhiteTiles(tiles [][]int, carpetLen int) int {
sort.Slice(tiles, func(i, j int) bool { return tiles[i][0] < tiles[j][0] })
n := len(tiles)
s, ans := 0, 0
for i, j := 0, 0; i < n; i++ {
for j < n && tiles[j][1]-tiles[i][0]+1 <= carpetLen {
s += tiles[j][1] - tiles[j][0] + 1
j++
}
if j < n && tiles[i][0]+carpetLen > tiles[j][0] {
ans = max(ans, s+tiles[i][0]+carpetLen-tiles[j][0])
} else {
ans = max(ans, s)
}
s -= (tiles[i][1] - tiles[i][0] + 1)
}
return ans
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。