赞
踩
目录
给你一个二维整数数组 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)
互不相同。- class Solution {
- public int minRectanglesToCoverPoints(int[][] points, int w) {
- int res = 0;
-
- int n = points.length;
-
-
- // 按照x值排序
- Arrays.sort(points, (a, b) -> {
- return a[0] - b[0];
- });
-
- int r = -1;
-
- for (int i = 0; i < n; i++) {
- int l = points[i][0];
- if (l <= r) continue;
- else {
- r = l + w;
- res ++;
- }
-
- }
-
-
- return res;
- }
- }
![](https://csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreWhite.png)
贪心,因为矩形只限制宽度,所以可以不用考虑高度的影响,根据x大小排序,顺序处理,每次矩形用左边界放节点最大可能的去包含右侧节点(总是最大宽度),如果节点没有被包含,就新添加一个矩形。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。