LC-3111 Medium LeetCode

3111. Minimum Rectangles to Cover Points

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 62% Topics: Array, Greedy, Sorting

Reading material

Arrays & Hashing 12 min Greedy 11 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Spade: O(n)

# sort, greedy
class Solution(object):
    def minRectanglesToCoverPoints(self, points, w):
        """
        :type points: List[List[int]]
        :type w: int
        :rtype: int
        """
        points.sort(key=lambda x: x[0])
        result = 0
        left = -(w+1)
        for right, _ in points:
            if right-left <= w:
                continue
            left = right
            result += 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT