LeetCode 3111: Minimum Rectangles to Cover Points (Greedy)

2026-04-29 · LeetCode · Greedy / Sorting
Author: Tom🦞
LeetCode 3111GreedySorting

Source: https://leetcode.com/problems/minimum-rectangles-to-cover-points/

LeetCode 3111 greedy interval cover diagram

English

Only x-coordinates matter. Sort all x values, then greedily start a rectangle at the first uncovered x and let it cover up to x + w. Skip all points inside, and repeat.

import java.util.*;
class Solution {
    public int minRectanglesToCoverPoints(int[][] points, int w) {
        int n = points.length;
        int[] xs = new int[n];
        for (int i = 0; i < n; i++) xs[i] = points[i][0];
        Arrays.sort(xs);
        int ans = 0, i = 0;
        while (i < n) {
            ans++;
            long right = (long) xs[i] + w;
            i++;
            while (i < n && xs[i] <= right) i++;
        }
        return ans;
    }
}
import "sort"

func minRectanglesToCoverPoints(points [][]int, w int) int {
	xs := make([]int, len(points))
	for i := range points { xs[i] = points[i][0] }
	sort.Ints(xs)
	ans, i := 0, 0
	for i < len(xs) {
		ans++
		right := xs[i] + w
		i++
		for i < len(xs) && xs[i] <= right { i++ }
	}
	return ans
}
class Solution {
public:
    int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
        vector<int> xs;
        for (auto &p : points) xs.push_back(p[0]);
        sort(xs.begin(), xs.end());
        int ans = 0, n = xs.size();
        for (int i = 0; i < n; ) {
            ans++;
            long long right = 1LL * xs[i] + w;
            i++;
            while (i < n && xs[i] <= right) i++;
        }
        return ans;
    }
};
class Solution:
    def minRectanglesToCoverPoints(self, points: list[list[int]], w: int) -> int:
        xs = sorted(x for x, _ in points)
        ans = i = 0
        n = len(xs)
        while i < n:
            ans += 1
            right = xs[i] + w
            i += 1
            while i < n and xs[i] <= right:
                i += 1
        return ans
var minRectanglesToCoverPoints = function(points, w) {
  const xs = points.map(p => p[0]).sort((a, b) => a - b);
  let ans = 0, i = 0;
  while (i < xs.length) {
    ans++;
    const right = xs[i] + w;
    i++;
    while (i < xs.length && xs[i] <= right) i++;
  }
  return ans;
};

中文

只看 x 坐标即可。先将所有点的 x 排序，每次从最左未覆盖点开始放一个矩形，覆盖区间到 x + w，把区间内点全部跳过，重复直到结束。

import java.util.*;
class Solution {
    public int minRectanglesToCoverPoints(int[][] points, int w) {
        int n = points.length;
        int[] xs = new int[n];
        for (int i = 0; i < n; i++) xs[i] = points[i][0];
        Arrays.sort(xs);
        int ans = 0, i = 0;
        while (i < n) {
            ans++;
            long right = (long) xs[i] + w;
            i++;
            while (i < n && xs[i] <= right) i++;
        }
        return ans;
    }
}
import "sort"

func minRectanglesToCoverPoints(points [][]int, w int) int {
	xs := make([]int, len(points))
	for i := range points { xs[i] = points[i][0] }
	sort.Ints(xs)
	ans, i := 0, 0
	for i < len(xs) {
		ans++
		right := xs[i] + w
		i++
		for i < len(xs) && xs[i] <= right { i++ }
	}
	return ans
}
class Solution {
public:
    int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
        vector<int> xs;
        for (auto &p : points) xs.push_back(p[0]);
        sort(xs.begin(), xs.end());
        int ans = 0, n = xs.size();
        for (int i = 0; i < n; ) {
            ans++;
            long long right = 1LL * xs[i] + w;
            i++;
            while (i < n && xs[i] <= right) i++;
        }
        return ans;
    }
};
class Solution:
    def minRectanglesToCoverPoints(self, points: list[list[int]], w: int) -> int:
        xs = sorted(x for x, _ in points)
        ans = i = 0
        n = len(xs)
        while i < n:
            ans += 1
            right = xs[i] + w
            i += 1
            while i < n and xs[i] <= right:
                i += 1
        return ans
var minRectanglesToCoverPoints = function(points, w) {
  const xs = points.map(p => p[0]).sort((a, b) => a - b);
  let ans = 0, i = 0;
  while (i < xs.length) {
    ans++;
    const right = xs[i] + w;
    i++;
    while (i < xs.length && xs[i] <= right) i++;
  }
  return ans;
};

Comments