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

题目描述：

给你一个二维整数数组 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 <= 105
• points[i].length == 2
• 0 <= xi == points[i][0] <= 109
• 0 <= yi == points[i][1] <= 109
• 0 <= w <= 109
• 所有点坐标 (xi, yi) 互不相同。

---

解题分析及思路：

方法：排序 + 贪心

思路：

由于矩阵只有宽度限制，没有高度限制，所以无需考虑纵坐标，那么所有的点映射在横坐标上，就是一个一维数组。

那么题目就变成覆盖一维数组的最小矩形数目。

利用贪心的思想，将第一个点作为矩形的左下角，然后遍历数组

• 如果当前点的横坐标小于上一个矩形的右下角，说明当前点在矩形内，无需增加矩形数目，直接跳过即可。
• 如果当前点的横坐标大于等于上一个矩形的右下角，说明当前点在矩形外，则将当前点作为新的矩形的左下角，并且结果+1，

如此往复，直到遍历完数组。

func minRectanglesToCoverPoints(points [][]int, w int) int {
	sort.Slice(points, func(i, j int) bool {
		return points[i][0] < points[j][0]
	})
	var right = points[0][0] + w
	var result = 1
	for index := range points {
		if points[index][0] > right {
			result++
			right = points[index][0] + w
		}
	}
	return result
}

复杂度：

• 时间复杂度：O(n * log n)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:144 ms,击败了65.12% 的Go用户
• 内存消耗:17.1 MB,击败了30.23% 的Go用户