Skip to content

2271. Maximum White Tiles Covered by a Carpet

Difficulty Topics

Description

You are given a 2D integer array tiles where tiles[i] = [li, ri] represents that every tile j in the range li <= j <= ri 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.

 

Example 1:

Input: tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
Output: 9
Explanation: Place the carpet starting on tile 10. 
It covers 9 white tiles, so we return 9.
Note that there may be other places where the carpet covers 9 white tiles.
It can be shown that the carpet cannot cover more than 9 white tiles.

Example 2:

Input: tiles = [[10,11],[1,1]], carpetLen = 2
Output: 2
Explanation: Place the carpet starting on tile 10. 
It covers 2 white tiles, so we return 2.

 

Constraints:

  • 1 <= tiles.length <= 5 * 104
  • tiles[i].length == 2
  • 1 <= li <= ri <= 109
  • 1 <= carpetLen <= 109
  • The tiles are non-overlapping.

Solution

maximum-white-tiles-covered-by-a-carpet.py
class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        prefix = [0]
        start = []
        tiles.sort()
        res = 0

        for x, y in tiles:
            prefix.append(prefix[-1] + y - x + 1)
            start.append(x)

        for i, (x, y) in enumerate(tiles):
            if y - x + 1 >= carpetLen:
                return carpetLen

            index = bisect_right(start, x + carpetLen) - 1
            x2, y2 = tiles[index]
            extra = 0

            if y2 - x + 1 >= carpetLen:
                extra = y2 - x + 1 - carpetLen


            total = prefix[index + 1] - prefix[i] - extra
            res = max(res, total)

        return res