Skip to content

2271. Maximum White Tiles Covered by a Carpet

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:

img

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:

img

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.

Intuition: it's always better to place a carpet at the beginning of a range. The reason is: if you shift a carpet one tile right, you might cover another white tile, but you definitely uncover the previous white tile.

So, we sort tile ranges, and check how many white tiles we can cover, starting from the beginning of each range.

To avoid TLE, we "drag" our carpet left-to-right, using the sliding window technique. It's a bit tricky for this problem:

We track the placement of the carpet in j (so the left side is tiles[j][0]). When we can cover tiles[i], we add those tiles to cover and extend the sliding window (++i). Otherwise, we compute partial cover of tiles[i] (total cover is cover + partial). We remove tiles[j] from cover. We move the carpet to the next tile (++j), shrinking the sliding window.

image

import java.util.Arrays;

class Solution {
    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        // Sort the tiles based on the starting position
        Arrays.sort(tiles, (a, b) -> (a[0] - b[0]));

        int res = 0; // To store the maximum number of white tiles covered
        int j = 0;   // The start of the sliding window
        int cover = 0; // To store the number of tiles covered in the current window

        for (int i = 0; res < carpetLen && i < tiles.length; ) {
            // If the carpet can fully cover the current tile
            if (tiles[j][0] + carpetLen > tiles[i][1]) {
                // Add the full length of the tile to the current coverage
                cover = cover + (tiles[i][1] - tiles[i][0] + 1);
                res = Math.max(res, cover);
                i++; // Move to the next tile
            } else {
                // Calculate the partial coverage if the carpet partially covers the current tile
                int partial = Math.max(0, tiles[j][0] + carpetLen - tiles[i][0]);
                res = Math.max(res, cover + partial);
                // Remove the first tile in the window from coverage and move the window
                cover = cover- (tiles[j][1] - tiles[j][0] + 1);
                j++;
            }
        }
        return res;
    }
}

// TC: O(nlogn)
// SC: O(1)

class Solution {
    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        Arrays.sort(tiles, (a, b) -> a[0] - b[0]);

        int n = tiles.length;
        int[] prefixSum = new int[n];

        for (int i = 0; i < n; i++){
            if (i == 0){
                prefixSum[i] = tiles[i][1] - tiles[i][0] + 1;
            }else{
                prefixSum[i] = prefixSum[i - 1] + (tiles[i][1] - tiles[i][0] + 1);
            }
        }

        int maxCoveredTiles = 0;
        int j = 0; // right limit

        for (int i = 0; i < n; i++){
            while(j < n && tiles[i][0] + carpetLen - 1 >= tiles[j][1]){
                j++;
            }

            int coveredLength = 0;
            if (i == 0){
                if (j > 0){
                    coveredLength = coveredLength + prefixSum[j - 1];
                }
            }else {
                if (j > i){
                    coveredLength = coveredLength + (prefixSum[j - 1] - prefixSum[i - 1]);
                }
            }

            if (j < n){
                coveredLength = coveredLength + Math.max(0, tiles[i][0] + carpetLen - 1 - tiles[j][0] + 1);
            }

            maxCoveredTiles = Math.max(maxCoveredTiles, coveredLength);
        }

        return maxCoveredTiles;
    }
}

呜呜呜 理解不了...