We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Rectangles to Cover Points

Number: 3390

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

Given a set of distinct points on a 2D plane and an integer w, cover all the points using the minimum number of rectangles. Each rectangle has its lower side on the x-axis (y = 0) with a left end at (x1, 0) and an upper end at (x2, y2) such that x1 <= x2, y2 >= 0, and the horizontal width constraint x2 - x1 <= w holds. A point is covered if it lies within or on the boundary of some rectangle. The objective is to determine the minimum number of such rectangles required to cover all the given points.

Key Insights

  • The vertical coverage of a rectangle can always be extended to cover the highest point within its horizontal interval, so the y-coordinates do not affect the placement horizontally.
  • The problem essentially reduces to covering points (based on their x-coordinates) with intervals of length w.
  • A greedy algorithm works by sorting the points by their x-coordinate and placing a rectangle starting at the leftmost uncovered point, covering as many points as possible within x + w.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the points. Space Complexity: O(n) for storing the sorted points (or O(1) additional space if sorting in-place).

Solution

Sort the points by their x-coordinate. Start with the leftmost point and place a rectangle that covers all points with x-coordinates in the interval [start, start+w]. Skip all points covered by this rectangle and then choose the next uncovered point to place another rectangle. Continue until all points are covered. This greedy strategy guarantees the minimal number of rectangles since each rectangle is maximally extended to include as many points as possible within the allowed width.

Code Solutions

def min_rectangles_to_cover_points(points, w):
    # Sort the points based on the x-coordinate
    points.sort(key=lambda point: point[0])
    count = 0
    i = 0
    n = len(points)
    # Process each point using a greedy strategy
    while i < n:
        # The left-most uncovered point's x coordinate
        start_x = points[i][0]
        # This rectangle can cover points up to start_x + w
        end_x = start_x + w
        # Move the pointer i while points are covered by the current rectangle
        while i < n and points[i][0] <= end_x:
            i += 1
        count += 1  # Place one rectangle
    return count

# Example usage:
points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]]
w = 1
print(min_rectangles_to_cover_points(points, w))  # Expected output: 2
← Back to All Questions