_3111. Minimum Rectangles to Cover Points.md

3111. Minimum Rectangles to Cover Points

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 21, 2024

Last updated : July 21, 2024

---

Related Topics : Array, Greedy, Sorting

Acceptance Rate : 63.04 %

---

Solutions

• m3111.java
• m3111.py

Java

m3111.java

class Solution {
    public int minRectanglesToCoverPoints(int[][] points, int w) {
        int[] xVals = new int[points.length];
        for (int i = 0; i < points.length; i++) {
            xVals[i] = points[i][0];
        }

        Arrays.sort(xVals);

        int prev = w * -1 - 1;
        int counter = 0;

        for (int i : xVals) {
            if (i - prev > w) {
                prev = i;
                counter++;
            }
        }

        return counter;

    }
}

Python

m3111.py

class Solution:
    def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
        counter = 0

        prev = -inf
        for x in sorted([x[0] for x in points]) :
            if x - prev <= w :
                continue
            counter += 1
            prev = x

        return counter