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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum White Tiles Covered by a Carpet

Difficulty: Medium

Problem Description

You are given a 2D integer array tiles where tiles[i] = [l_i, r_i] represents that every tile j in the range l_i <= j <= r_i is colored white. You are also given an integer carpetLen, the length of a single carpet that can be placed anywhere. Return the maximum number of white tiles that can be covered by the carpet.

Key Insights

  • The problem requires determining the optimal placement of a carpet over a series of non-overlapping tiles to maximize coverage.
  • Sorting the tiles by their starting positions allows for efficient searching and coverage calculation.
  • A sliding window approach helps in determining the maximum coverage of white tiles as the carpet moves across the ranges.
  • Prefix sums can be used to quickly calculate the number of covered tiles without needing to iterate through every tile range repeatedly.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting of the tiles, where n is the number of tiles. The subsequent coverage calculation can be done in O(n) time. Space Complexity: O(n) for storing the sorted tiles and any additional data structures used for calculations.

Solution

To solve this problem, we will:

  1. Sort the tiles based on their starting positions.
  2. Utilize a sliding window approach to determine how many tiles can be covered by the carpet when placed at different starting points.
  3. Maintain a running total of the number of white tiles covered using prefix sums to optimize the coverage calculation.

Code Solutions

def maxWhiteTiles(tiles, carpetLen):
    # Sort tiles based on their starting position
    tiles.sort()
    n = len(tiles)
    
    # Generate prefix sums for the lengths of the tiles
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + (tiles[i][1] - tiles[i][0] + 1)
    
    max_covered = 0
    left = 0
    
    for right in range(n):
        # While the carpet can't cover the current range, move the left pointer
        while tiles[right][1] - tiles[left][0] + 1 > carpetLen:
            left += 1
        
        # Calculate the number of covered tiles
        covered_tiles = prefix_sum[right + 1] - prefix_sum[left]
        max_covered = max(max_covered, covered_tiles)
        
        # Check if we can extend the carpet to the right
        if left > 0:
            # Adjust for the overlap with the left tile
            overlap = max(0, tiles[left - 1][1] - tiles[right][0] + 1)
            max_covered = max(max_covered, covered_tiles - overlap)
    
    return max_covered
← Back to All Questions