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

题目描述

给你一个二维整数数组 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) 互不相同。

解法

方法一：贪心 + 排序

思考

矩形高度不受限，覆盖只由横坐标与宽度 \(w\) 决定。若枚举每个点所属矩形的划分，状态随点数指数增长。

最优策略是按 \(x\) 排序后尽量把当前矩形向右铺满：一旦某点落在已覆盖范围外，必须新开一个以该点为左端、长度为 \(w\) 的矩形。

为此排序后维护当前矩形右边界 \(x_1\)，遇 \(x>x_1\) 则答案加一并令 \(x_1=x+w\)。贪心覆盖次数即为最少矩形数。

根据题目描述，我们不需要考虑矩形的高度，只需要考虑矩形的宽度。

我们可以将所有的点按照横坐标进行排序，用一个变量 \(x_1\) 记录当前矩形所能覆盖的最右边的横坐标，初始时 \(x_1 = -1\)。

接下来我们遍历所有的点，如果当前点的横坐标 \(x\) 大于 \(x_1\)，说明已有的矩形无法覆盖当前点，我们就需要增加一个矩形，答案加一，然后我们更新 \(x_1 = x + w\)。

遍历完成后，我们就得到了最少需要的矩形数目。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是点的数量。

Python3JavaC++GoTypeScriptRustC#

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

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

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

func minRectanglesToCoverPoints(points [][]int, w int) (ans int) {
    sort.Slice(points, func(i, j int) bool { return points[i][0] < points[j][0] })
    x1 := -1
    for _, p := range points {
        if x := p[0]; x > x1 {
            ans++
            x1 = x + w
        }
    }
    return
}

function minRectanglesToCoverPoints(points: number[][], w: number): number {
    points.sort((a, b) => a[0] - b[0]);
    let [ans, x1] = [0, -1];
    for (const [x, _] of points) {
        if (x > x1) {
            ++ans;
            x1 = x + w;
        }
    }
    return ans;
}

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

public class Solution {
    public int MinRectanglesToCoverPoints(int[][] points, int w) {
        Array.Sort(points, (a, b) => a[0] - b[0]);
        int ans = 0, x1 = -1;
        foreach (int[] p in points) {
            int x = p[0];
            if (x > x1) {
                ans++;
                x1 = x + w;
            }
        }
        return ans;
    }
}

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

题目描述

解法

方法一：贪心 + 排序

评论