Skip to content

3111. Minimum Rectangles to Cover Points 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
    int ans = 0;
    int prevX = -w - 1;
    vector<int> xs;

    for (const vector<int>& point : points) {
      const int x = point[0];
      xs.push_back(x);
    }

    ranges::sort(xs);

    for (const int x : xs)
      if (x > prevX + w) {
        ++ans;
        prevX = x;
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int minRectanglesToCoverPoints(int[][] points, int w) {
    int ans = 0;
    int prevX = -w - 1;
    int[] xs = new int[points.length];

    for (int i = 0; i < points.length; ++i)
      xs[i] = points[i][0];

    Arrays.sort(xs);

    for (final int x : xs)
      if (x > prevX + w) {
        ++ans;
        prevX = x;
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def minRectanglesToCoverPoints(self, points: list[list[int]], w: int) -> int:
    ans = 0
    prevX = -w - 1
    xs = sorted([x for x, _ in points])

    for x in xs:
      if x > prevX + w:
        ans += 1
        prevX = x

    return ans