覆盖所有点的最少矩形数目

100280. 覆盖所有点的最少矩形数目

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

每个矩形的左下角在某个点 (x₁, 0) 处，且右上角在某个点 (x₂, y₂) 处，其中 x₁ <= x₂ 且 y₂ >= 0 ，同时对于每个矩形都必须满足 x₂ - x₁ <= 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 <= 10⁵
points[i].length == 2
0 <= x_i == points[i][0] <= 10⁹
0 <= y_i == points[i][1] <= 10⁹
0 <= w <= 10⁹
所有点坐标 (x_i, y_i) 互不相同。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) { } };

javascript 解法, 执行用时: 170 ms, 内存消耗: 82.8 MB, 提交时间: 2024-07-31 09:29:25

/**
 * @param {number[][]} points
 * @param {number} w
 * @return {number}
 */
var minRectanglesToCoverPoints = function(points, w) {
    points.sort((p, q) => p[0] - q[0]);
    let ans = 0;
    let x2 = -1;
    for (const [x, _] of points) {
        if (x > x2) {
            ans++;
            x2 = x + w;
        }
    }
    return ans;
};

rust 解法, 执行用时: 24 ms, 内存消耗: 10.4 MB, 提交时间: 2024-07-31 09:29:05

impl Solution {
    pub fn min_rectangles_to_cover_points(mut points: Vec<Vec<i32>>, w: i32) -> i32 {
        points.sort_unstable_by(|p, q| p[0].cmp(&q[0]));
        let mut ans = 0;
        let mut x2 = -1;
        for p in points {
            if p[0] > x2 {
                ans += 1;
                x2 = p[0] + w;
            }
        }
        ans
    }
}

java 解法, 执行用时: 4 ms, 内存消耗: 96 MB, 提交时间: 2024-04-15 14:22:54

class Solution {
    public int minRectanglesToCoverPoints(int[][] points, int w) {
        Arrays.sort(points, (p, q) -> p[0] - q[0]);
        int ans = 0;
        int x2 = -1;
        for (int[] p : points) {
            if (p[0] > x2) {
                ans++;
                x2 = p[0] + w;
            }
        }
        return ans;
    }
}

cpp 解法, 执行用时: 269 ms, 内存消耗: 115.6 MB, 提交时间: 2024-04-15 14:22:18

class Solution {
public:
    int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
        ranges::sort(points, [](const auto& p, const auto& q) {
            return p[0] < q[0];
        });
        int ans = 0;
        int x2 = -1;
        for (auto& p : points) {
            if (p[0] > x2) {
                ans++;
                x2 = p[0] + w;
            }
        }
        return ans;
    }
};

golang 解法, 执行用时: 125 ms, 内存消耗: 15.2 MB, 提交时间: 2024-04-15 14:22:05

func minRectanglesToCoverPoints(points [][]int, w int) (ans int) {
	slices.SortFunc(points, func(p, q []int) int { return p[0] - q[0] })
	x2 := -1
	for _, p := range points {
		if p[0] > x2 {
			ans++
			x2 = p[0] + w
		}
	}
	return
}

python3 解法, 执行用时: 99 ms, 内存消耗: 53.5 MB, 提交时间: 2024-04-15 14:21:49

# 贪心解法，只考虑横坐标
class Solution:
    def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
        points.sort(key=lambda p: p[0])
        ans = 0
        x2 = -1
        for x, _ in points:
            if x > x2:
                ans += 1
                x2 = x + w
        return ans

上一题

下一题

详情