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)
互不相同。
解法
方法一:贪心 + 排序
根据题目描述,我们不需要考虑矩形的高度,只需要考虑矩形的宽度。
我们可以将所有的点按照横坐标进行排序,用一个变量 $x_1$ 记录当前矩形的左下角的横坐标。然后遍历所有的点,如果当前点的横坐标 $x$ 比 $x_1 + w$ 大,说明当前点不能被当前的矩形覆盖,我们就需要增加一个新的矩形,然后更新 $x_1$ 为当前点的横坐标。
遍历完成后,我们就得到了最少需要多少个矩形。
时间复杂度 $O(n \times \log n)$,空间复杂度 $O(\log n)$。其中 $n$ 是点的数量。
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|