友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
3111. 覆盖所有点的最少矩形数目
给你一个二维整数数组 point ，其中 points[i] = [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。
每个矩形的左下角在某个点 (x1, 0) 处，且右上角在某个点 (x2, y2) 处，其中 x1 <= x2 且 y2 >= 0 ，同时对于每个矩形都 必须 满足 x2 - x1 <= w 。
如果一个点在矩形内或者在边上，我们说这个点被矩形覆盖了。
请你在确保每个点都 至少 被一个矩形覆盖的前提下，最少 需要多少个矩形。
注意：一个点可以被多个矩形覆盖。
示例 1：
输入： points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1
输出： 2
解释：
上图展示了一种可行的矩形放置方案：
-
一个矩形的左下角在
(1, 0)，右上角在(2, 8)。 -
一个矩形的左下角在
(3, 0)，右上角在(4, 8)。
示例 2：
输入： points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2
输出： 3
解释：
上图展示了一种可行的矩形放置方案：
-
一个矩形的左下角在
(0, 0)，右上角在(2, 2)。 -
一个矩形的左下角在
(3, 0)，右上角在(5, 5)。 -
一个矩形的左下角在
(6, 0)，右上角在(6, 6)。
示例 3：
输入： points = [[2,3],[1,2]], w = 0
输出： 2
解释：
上图展示了一种可行的矩形放置方案：
-
一个矩形的左下角在
(1, 0)，右上角在(1, 2)。 -
一个矩形的左下角在
(2, 0)，右上角在(2, 3)。
提示：
-
1 <= points.length <= 105 -
points[i].length == 2 -
0 <= xi == points[i][0] <= 109 -
0 <= yi == points[i][1] <= 109 -
0 <= w <= 109 -
所有点坐标
(xi, yi)互不相同。
思路分析
由于矩形的高没有限制，所以我们只需考虑点的横坐标。
矩形越宽，覆盖的点越多，所以 x2 应该恰好等于 x1+w。
从左边界开始，尽可能多占用横轴。宽度耗尽，则从下一个点开始。
目前使用的办法是统计最小最大值，然后在区间内进行遍历。这样会空耗很多数字。另外一个办法是对输入按照 X 轴排序。这样就不需要空转很多数字。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-21 22:07:28
*/
public int minRectanglesToCoverPoints(int[][] points, int w) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
Map<Integer, Integer> x2y = new HashMap<>();
for (int[] point : points) {
int x = point[0];
int y = point[1];
min = Math.min(min, x);
max = Math.max(max, x);
x2y.put(x, Math.max(x2y.getOrDefault(x, 0), y));
}
if (w == 0) {
return x2y.size();
}
int result = 0;
int iw = w;
boolean flag = false;
for (int i = min; i <= max; i++) {
if (!flag && x2y.containsKey(i)) {
flag = true;
}
if (flag) {
iw--;
}
if (iw < 0 || i == max) {
result++;
flag = false;
iw = w;
}
}
return result;
}