3111：覆盖所有点的最少矩形数目（1401 分）

力扣第 128 场双周赛第 2 题

题目

给你一个二维整数数组 point ，其中 points[i] = [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。

每个矩形的左下角在某个点 (x1, 0) 处，且右上角在某个点 (x2, y2) 处，其中 x1 <= x2 且 y2 >= 0 ，同时对于每个矩形都 必须 满足 x2 - x1 <= w 。

如果一个点在矩形内或者在边上，我们说这个点被矩形覆盖了。

请你在确保每个点都 至少 被一个矩形覆盖的前提下，最少 需要多少个矩形。

注意：一个点可以被多个矩形覆盖。

示例 1：

示例 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) 互不相同。

相似问题：

• 0939：最小面积矩形（1752 分）
• 0973：最接近原点的 K 个点（1213 分）

分析

• 矩形高度没有限制，因此只需要考虑 x 坐标
• 贪心遍历即可

解答

1
2
3
4
5
6
7
8

class Solution:
    def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
        res,x = 0,-inf
        for y,_ in sorted(points):
            if y>x+w:
                res += 1
                x = y
        return res

111 ms