Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2271.html

2271. Maximum White Tiles Covered by a Carpet

  • Difficulty: Medium.
  • Related Topics: Array, Binary Search, Greedy, Sorting, Prefix Sum.
  • Similar Questions: Maximum Number of Vowels in a Substring of Given Length.

Problem

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 (Java, C++, Python)

  • class Solution {
    public int maximumWhiteTiles(int[][] tiles, int carpetLength) {
        Arrays.sort(tiles, Comparator.comparingInt(x -> x[0]));
        int currentCover = Math.min(tiles[0][1] - tiles[0][0] + 1, carpetLength);
        int maxCover = currentCover;
        int head = 1;
        int tail = 0;
        while (tail < tiles.length && head < tiles.length && maxCover < carpetLength) {
            if (tiles[head][1] - tiles[tail][0] + 1 <= carpetLength) {
                currentCover += tiles[head][1] - tiles[head][0] + 1;
                maxCover = Math.max(maxCover, currentCover);
                ++head;
            } else {
                int possiblePartialCoverOverCurrentHead =
                        carpetLength - (tiles[head][0] - tiles[tail][0]);
                maxCover = Math.max(maxCover, currentCover + possiblePartialCoverOverCurrentHead);
                currentCover = currentCover - (tiles[tail][1] - tiles[tail][0] + 1);
                ++tail;
            }
        }
        return maxCover;
    }
}

  • Todo

  • class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        tiles.sort()
        n = len(tiles)
        s = ans = j = 0
        for i, (li, ri) in enumerate(tiles):
            while j < n and tiles[j][1] - li + 1 <= carpetLen:
                s += tiles[j][1] - tiles[j][0] + 1
                j += 1
            if j < n and li + carpetLen > tiles[j][0]:
                ans = max(ans, s + li + carpetLen - tiles[j][0])
            else:
                ans = max(ans, s)
            s -= ri - li + 1
        return ans

############

# 2271. Maximum White Tiles Covered by a Carpet
# https://leetcode.com/problems/maximum-white-tiles-covered-by-a-carpet/

class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        res = 0
        tiles.sort()
        
        prefix = [0]
        for x, y in tiles:
            prefix.append(prefix[-1] + y - x + 1)
        
        startPos = [x for x, _ in tiles]
        
        for i, (x, y) in enumerate(tiles):
            if y - x + 1 >= carpetLen:
                return carpetLen
        
            endIndex = bisect.bisect(startPos, x + carpetLen - 1) - 1
            ex, ey = tiles[endIndex]
            
            extra = 0
            
            if ey - x + 1 > carpetLen:
                extra = ey - x - carpetLen + 1
            
            res = max(res, prefix[endIndex + 1] - prefix[i] - extra)
        
        return res

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions