LeetCode 题解工作台
覆盖所有点的最少矩形数目
给你一个二维整数数组 point ，其中 points[i] = [x i , y i ] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。 每个矩形的左下角在某个点 (x 1 , 0) 处，且右上角在某个点 (x 2 , y 2 ) 处，其中 x 1 2 且 y 2 >…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
根据题目描述，我们不需要考虑矩形的高度，只需要考虑矩形的宽度。 我们可以将所有的点按照横坐标进行排序，用一个变量 记录当前矩形所能覆盖的最右边的横坐标，初始时 $x_1 = -1$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个二维整数数组 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 <= 105points[i].length == 20 <= xi == points[i][0] <= 1090 <= yi == points[i][1] <= 1090 <= w <= 109- 所有点坐标
(xi, yi)互不相同。
解题思路
方法一：贪心 + 排序
根据题目描述，我们不需要考虑矩形的高度，只需要考虑矩形的宽度。
我们可以将所有的点按照横坐标进行排序，用一个变量 记录当前矩形所能覆盖的最右边的横坐标，初始时 。
接下来我们遍历所有的点，如果当前点的横坐标 大于 ，说明已有的矩形无法覆盖当前点，我们就需要增加一个矩形，答案加一，然后我们更新 。
遍历完成后，我们就得到了最少需要的矩形数目。
时间复杂度 ，空间复杂度 。其中 是点的数量。
class Solution:
def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
points.sort()
ans, x1 = 0, -1
for x, _ in points:
if x > x1:
ans += 1
x1 = x + w
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate understands the significance of sorting the points by the x-coordinate.
- question_mark
Observe if the candidate uses the greedy method efficiently to cover points.
- question_mark
Evaluate whether the candidate correctly handles the width constraint during rectangle placement.
常见陷阱
外企场景- error
Overcomplicating the problem by trying to account for y-coordinates, which are not needed.
- error
Not recognizing that sorting is the first step, which could lead to inefficient rectangle placements.
- error
Failing to increment the rectangle count correctly after each placement, leading to inaccurate results.
进阶变体
外企场景- arrow_right_alt
Handling edge cases where points are already aligned on a single vertical line.
- arrow_right_alt
Adjusting the rectangle width dynamically instead of using a fixed w value.
- arrow_right_alt
Optimizing the solution for larger point sets, potentially using a divide-and-conquer approach.