算法基础算法

范围缩放法证明贪心的正确性

字数统计: 1.5k字   |   阅读时长: 5分
, ,

摘要: 范围缩放法例子

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文看一个比较简单的贪心算法的问题，思路和算法很好想。这个题值得分享的亮点是这是使用范围缩放法证明贪心正确性的例子。

范围缩放法的思路是如果任何对局部最优策略作用范围的扩展都不会造成整体结果变差。那么就尽量将作用范围扩展即可。

题目

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

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

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

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

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

提示：

1
2
3
4
5
6
1 <= points.length <= 1e5
points[i].length == 2
0 <= xi == points[i][0] <= 1e9
0 <= yi == points[i][1] <= 1e9
0 <= w <= 1e9
所有点坐标 (xi, yi) 互不相同。

示例 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) 。

题解

算法：贪心、扫描线

根据题目描述和实例，矩形的高度是不限的，只有宽度有一个 $x_{2} - x_{1} \leq w$ 的限制。此外每个矩形可以有不同的尺寸，矩形的左下角和右上角不一定恰好是 points 中的点。

基于前面这些条件，我们发现制约矩形数量的只有宽度限制这一个条件，也就是说假设矩形的左边界在 $x_{1}$ 处，那么 $x_{1} \leq x \leq x1 + w$ 范围内的所有 points 中的点都可以用一个矩形覆盖到。

因此我们可以将所有点按照横坐标排序，假设排序后的横坐标为 $x_{1}, x_{2}, \cdots, x_{n}$，然后从左到右开始覆盖。

刚开始时最左边尚未覆盖的横坐标为 $x_{1}$，矩形的左边界就设为 $x_{1}$，然后从左到右依次枚举，直至枚举到第 $p_{1}$ 个横坐标 $x_{p_{1}}$，有 $x_{p_{1}} - x_{1}$，那么当前矩形的覆盖就结束了，然后从 $x_{p_{1}}$ 开始进行下一个矩形的覆盖，直至按顺序排列的所有横坐标耗尽。

假设用了 $m$ 个矩形，则这 $m$ 个矩形覆盖的点的横坐标分别为：

范围缩放法

范围缩放法的思路是：证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。那么就尽量将作用范围扩展即可。

上一个矩形覆盖完后，当前尚未覆盖的横坐标中最小的为 $x_{p_{j}}$，那么当前考虑的矩形的左边界不能大于 $x_{p_{j}}$，否则覆盖不到 $x_{p_{j}}$，下面考虑左边界小于 $x_{p_{j}}$ 的情况：

假设左边界小于 $x_{p_{j}}$，后续使用若干个矩形完成覆盖，后续矩形覆盖的横坐标分别为：

那么如果将左边界向右移动到 $x_{p_{j}}$，当前矩形至少也可以覆盖原有的 $(x_{p_{j}}, x_{p_{j+1}-1})$，还有可能向右多覆盖一些点。

由于一个点可以被多个矩形覆盖，因此后续的矩形至少依然可以按照上述覆盖方式完成整体的覆盖，矩形数不变。如果后续的矩形左边界向右移动，还有可能减少矩形个数。也就是说，尽可能将当前矩形左边界向右移动，至少不会使得结果更差，还有可能更好。因此每个矩形都尽量把左边界往左放即可。

每个矩形的宽度的选择也可以用范围缩放法论证，即将当前矩形的宽度变大，至少不会使得最终使用的矩形个数更多，因此每个矩形都尽量选择最大宽度的即可。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
        xs = [x for x, _ in points]
        xs.sort()
        n = len(xs)
        p = 0
        ans = 0
        while p < n:
            ans += 1
            r = p
            while r < n and xs[r] - xs[p] <= w:
                r += 1
            p = r
        return ans
Share