JZX轻语：简
LeetCode 3111 - 覆盖所有点的最少矩形数目
发表于2024年07月31日
该题目只涉及到x坐标，y坐标是无关紧要的(矩形无高度限制)。本质就是尽可能地使用最少的矩形，使得其宽度覆盖所有的点。可先对所有点的x坐标进行排序，然后使用贪心法，每次取出一个当前剩余的最大的x坐标(作为新矩形的右边界)，然后再取出尽可能多的x坐标填充在矩形内，使得其差值不超过w即可。
class Solution:
def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
x_list = sorted({x for x, _ in points})
ans = 0
while x_list:
r = x_list.pop()
while x_list and r - x_list[-1] <= w:
x_list.pop()
ans += 1
return ansC++的做法：
class Solution {
public:
int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
vector<int> x_list;
for (auto &point : points) x_list.push_back(point[0]);
sort(x_list.begin(), x_list.end());
int ans = 0;
int cur_index = x_list.size() - 1;
while (cur_index >= 0) {
auto r_bound = x_list[cur_index--];
while (cur_index >= 0 && r_bound - x_list[cur_index] <= w) cur_index--;
++ans;
}
return ans;
}
};