What is the main pattern in Maximum White Tiles Covered by a Carpet?

The practical pattern is sorted intervals plus targeted binary search over reachable coverage, not brute force over positions. You test carpet starts at tile boundaries, count fully covered intervals quickly, and then add one partial overlap at the edge.

Why can the carpet start be restricted to tile starts?

If a chosen carpet start lies inside a gap or inside an interval after its first white position, shifting it left to the nearest white interval start does not reduce covered white tiles. That means every optimal answer has an equivalent placement aligned to some tiles[i][0].

Is a sliding window also valid for problem 2271?

Yes. A two-pointer window over sorted intervals can maintain the total length of fully covered intervals and then compute the current partial overlap. It often achieves O(n) after sorting, while the binary-search version is slightly more direct to reason about from candidate starts.

Why do prefix sums help so much here?

Once intervals are sorted, prefix sums let you add the lengths of many fully covered intervals in constant time. Without them, each candidate carpet start would repeatedly sum the same interval lengths and turn an efficient solution into a slow one.

What is the easiest bug to make in this problem?

The most common bug is miscomputing the partial coverage of the last touched interval, especially with inclusive endpoints. Always compute overlap using max(left1, left2) and min(right1, right2), then add minRight - maxLeft + 1 only when that value is positive.

#2271

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

毯子覆盖的最多白色砖块数

给你一个二维整数数组 tiles ，其中 tiles[i] = [l i , r i ] ，表示所有在 l i i 之间的每个瓷砖位置 j 都被涂成了白色。同时给你一个整数 carpetLen ，表示可以放在任何位置的一块毯子的长度。请你返回使用这块毯子，最多可以盖住多少块白色瓷砖。示…

数组二分查找贪心滑动窗口排序

题目描述

给你一个二维整数数组 tiles ，其中 tiles[i] = [l_i, r_i] ，表示所有在 l_i <= j <= r_i 之间的每个瓷砖位置 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⁴
tiles[i].length == 2
1 <= l_i <= r_i <= 10⁹
1 <= carpetLen <= 10⁹
tiles 互相 不会重叠 。

lightbulb

解题思路

方法一：贪心 + 排序 + 滑动窗口

直觉上，毯子的左端点一定与某块瓷砖的左端点重合，这样才能使得毯子覆盖的瓷砖最多。

我们可以来简单证明一下。

如果毯子落在某块瓷砖的中间某个位置，将毯子右移一个，毯子覆盖的瓷砖数量可能减少，也可能不变，但不可能增加；将毯子左移一个，毯子覆盖的瓷砖数量可能不变，也可能增加，但不可能减少。

也就是说，将毯子左移至某块瓷砖的左端点，一定可以使得毯子覆盖的瓷砖数量最多。

因此，我们可以将所有瓷砖按照左端点从小到大排序，然后枚举每块瓷砖的左端点，计算出以该左端点为起点的毯子覆盖的瓷砖数量，取最大值即可。

为了计算以某块瓷砖的左端点为起点的毯子覆盖的瓷砖数量，我们可以使用滑动窗口的思想，维护一个右端点不断右移的窗口，窗口内的瓷砖数量即为毯子覆盖的瓷砖数量。

时间复杂度 $O(n\log n)$ ，其中 $n$ 为瓷砖的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
You notice that the carpet never needs to start in the middle of empty space or inside a gap between intervals.
question_mark
You convert interval lengths into prefix sums so fully covered segments are added without re-walking them.
question_mark
You explicitly handle the final partially covered interval instead of assuming every touched interval is fully counted.

warning

常见陷阱

外企场景

error
Trying to slide the carpet across every coordinate, which fails immediately because positions go up to 10^9.
error
Double counting the last interval when binary search finds an interval that is only partially covered.
error
Forgetting the inclusive endpoints, so overlap length should use end - start + 1 rather than end - start.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Replace one carpet with two carpets; then the interval DP or split-point preprocessing becomes the main extension.
arrow_right_alt
Allow overlapping tile intervals; then you must merge intervals first before applying the same coverage logic.
arrow_right_alt
Ask for the exact carpet start position instead of only the count; store the best starting interval while computing the maximum.

help

常见问题

外企场景

继续练习

#1838 最高频元素的频数 #2234 花园的最大总美丽值 #3413 收集连续 K 个袋子可以获得的最多硬币数量