本文涉及的基础知识点

C++二分查找

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

给你一个二维整数数组 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⁴

tiles[i].length == 2

1 <= li <= ri <= 10⁹

1 <= carpetLen <= 10⁹

tiles 互相 不会重叠 。

二分查找

规则二：毯子的左边界和一定和某段瓷砖的左边界(tiles[i][0])对齐。

条件三：能覆盖住x或更多的瓷砖。

本题有解大于等于x

⟺

\iff

⟺ 规则一下有解大于等于x。下面分别证明：充分性和必要性。

充分性：如果毯子的左边界在某段瓷砖上但不在此段的左边界。左移毯子，左边一定多覆盖一块瓷砖；右边最多少盖住一块瓷砖。

如果毯子的左边界不在瓷砖上，右移。左边覆盖的瓷砖没减少，右边可能增加。

必要性：规则一和本题规则的子集，本题规则下可以选择规则一的方案。

这就是《喜缺全书算法册》的证明一。

先对tiles排序。

枚举各瓷砖段tiles[i]，it指向第一个没覆盖的没砖段左端，lower_bound(…tiles[i]+carpetLen)，–it 就是被覆盖的最后一段。由于至少盖住了tiles[i]，所以–it一定合法。

totals记录个瓷砖段之前的瓷砖总数，不包括tiles[i]。令瓷砖覆盖了tiles[i…j]，则覆盖的数量：totals[j] - totals[i] + (end - tiles[j])

end = min(tiles[i]+carpetLen,tiles[j][1]+1) 毯子末端和最后一段瓷砖有三种关系：<=>。

代码

核心代码

<code>class Solution { -- -->

public:

int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {

sort(tiles.begin(), tiles.end());

int total = 0;

vector<int> totals;

for (const auto& v : tiles) {

totals.emplace_back(total);

total += v[1] - v[0] + 1;

}

int ret = 0;

for (int i = 0; i < tiles.size();i++ ) {

auto j = lower_bound(tiles.begin(), tiles.end(), tiles[i][0] + carpetLen,[&](vector<int>& v1, int val) { return v1[0] < val; }) - tiles.begin();

j--;

const int cur = totals[j] - totals[i] + (min(tiles[i][0] + carpetLen,tiles[j][1]+1) - tiles[j][0]);

ret = max(ret, cur);

}

return ret;

}

};

核心代码

vector<vector<int>> tiles;

int carpetLen;

TEST_METHOD(TestMethod11)

{

tiles = { { 1,5},{ 10,11},{ 12,18},{ 20,25},{ 30,32} }, carpetLen = 10;

auto res = Solution().maximumWhiteTiles(tiles, carpetLen);

AssertEx(9, res);

}

TEST_METHOD(TestMethod12)

{

tiles = { { 10,11},{ 1,1} }, carpetLen = 2;

auto res = Solution().maximumWhiteTiles(tiles, carpetLen);

AssertEx(2, res);

}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。