LeetCode Solutions Blog

Maximum White Tiles Covered by a Carpet

Number: 2359

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a list of non-overlapping white tile intervals, where each interval [l, r] represents that all positions j in the range l to r are white, and an integer carpetLen that represents the length of a carpet that can be placed anywhere, find the maximum number of white tiles that can be covered by the carpet.

Key Insights

Sort the tile intervals by their starting positions.
Precompute a prefix sum array for quick calculation of the total white tiles in a given range of intervals.
Use binary search to determine the farthest interval that is completely covered by a carpet starting at a given interval's start.
Account for a possibly partially covered interval at the end to calculate the exact number of white tiles covered.
The sliding window with binary search approach ensures efficiency even when there are many intervals.

Space and Time Complexity

Time Complexity: O(n log n) where n is the number of tile intervals (sorting and binary search in each iteration). Space Complexity: O(n) for storing the prefix sums and sorted intervals.

Solution

The solution starts by sorting the intervals. We then build a prefix sum array where each element represents the total number of white tiles from the start of the sorted list up to the current interval. For each interval, treat its start as a potential left boundary for placing the carpet. Using binary search, find the interval that the carpet reaches at the far end (start + carpetLen - 1). The fully covered intervals contribute their entire length (obtained from the prefix sum) and if a subsequent interval is only partially covered, add the overlapped portion. Update the maximum seen value over all possible placements.

Code Solutions

# Python code solution
class Solution:
    def maximumWhiteTiles(self, tiles, carpetLen):
        # Sort tiles by start of the interval
        tiles.sort(key=lambda x: x[0])
        n = len(tiles)
        # Create prefix sum for white tiles count for each interval
        prefix = [0] * (n + 1)
        for i in range(n):
            # Add the length of current interval to the prefix sum:
            # tile_length = r - l + 1
            prefix[i + 1] = prefix[i] + (tiles[i][1] - tiles[i][0] + 1)
        
        max_cover = 0
        # Iterate over each tile as the potential starting position for the carpet
        for i in range(n):
            start = tiles[i][0]
            # Calculate farthest coordinate that the carpet can cover
            end_position = start + carpetLen - 1
            # Binary search to find the rightmost interval whose end is <= end_position,
            # But we need to consider the possibility of partially covering an interval.
            lo, hi = i, n - 1
            j = i
            while lo <= hi:
                mid = (lo + hi) // 2
                if tiles[mid][1] <= end_position:
                    j = mid
                    lo = mid + 1
                else:
                    hi = mid - 1
            
            # Total white tiles that are completely covered from interval i to j
            total = prefix[j + 1] - prefix[i]
            
            # If there is an interval after j which might be partially covered by the carpet, add the overlap.
            if j + 1 < n:
                # The start of the next interval
                partial = max(0, end_position - tiles[j + 1][0] + 1)
                total += min(partial, tiles[j + 1][1] - tiles[j + 1][0] + 1)
            max_cover = max(max_cover, total)
        return max_cover

# Example usage:
# sol = Solution()
# print(sol.maximumWhiteTiles([[1,5],[10,11],[12,18],[20,25],[30,32]], 10))