Maximum White Tiles Covered by a Carpet LeetCode Solution

Problem – Maximum White Tiles Covered by a Carpet LeetCode Solution

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.

Maximum White Tiles Covered by a Carpet LeetCode Solution in C++

int maximumWhiteTiles(vector<vector<int>>& t, int len) {
    int res = 0, j = 0, cover = 0;
    sort(begin(t), end(t));
    for (int i = 0; res < len && i < t.size(); )
        if (t[j][0] + len > t[i][1]) {
            cover += t[i][1] - t[i][0] + 1;
            res = max(res, cover);
            ++i;
        }
        else {
            int partial = max(0, t[j][0] + len - t[i][0]);
            res = max(res, cover + partial);
            cover -= (t[j][1] - t[j][0] + 1);
            ++j;
        }
    return res;
}

Maximum White Tiles Covered by a Carpet LeetCode Solution in Python

class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        # sort the tiles by the starting position
        tiles.sort(key = lambda x:x[0])
        # build the starting position array
        startPos = [tiles[i][0] for i in range(len(tiles))]
        # build the prefix sum array
        preSum = [0] * (len(tiles) + 1)
        for i in range(1, len(tiles) + 1):
            preSum[i] = preSum[i - 1] + (tiles[i-1][1]-tiles[i-1][0] + 1)
        
        res = 0
        for i in range(len(tiles)):
            s, e = tiles[i]
            # if the length of tile >= length of carpet, return carpetLen
            if e >= s + carpetLen - 1:
                return carpetLen
            # binary search the index of the ending tile that the carpet can partially cover
            endIdx = bisect_right(startPos, s + carpetLen - 1) - 1
            # calculate the length of the ending tile that the carpet cannot cover 
            compensate = 0
            if tiles[endIdx][1] > s + carpetLen - 1:
                compensate = tiles[endIdx][1] - s - carpetLen + 1
            # update the result
            res = max(res, preSum[endIdx+1] - preSum[i] - compensate)
            
        return res

Maximum White Tiles Covered by a Carpet LeetCode Solution in Java

class Solution {
    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        Arrays.sort(tiles, Comparator.comparingInt(i -> i[0]));
        int rv = 0, overlap = 0, ei = 0, prevEnd = 0;
        for (int si = 0; si < tiles.length; si++) {
            int st = tiles[si][0], end = st + carpetLen - 1;
            if (si > 0) {
                overlap -= (Math.min(prevEnd, tiles[si-1][1]) - tiles[si-1][0] + 1);
            }
            if (ei-1 >= si && tiles[ei-1][1] > prevEnd) {
                overlap += (Math.min(end, tiles[ei-1][1]) - prevEnd);
            }
            
            while (ei < tiles.length && tiles[ei][0] <= end) {
                overlap += (Math.min(end, tiles[ei][1]) - tiles[ei][0] + 1);
                ei++;
            }
            
            prevEnd = end;
            rv = Math.max(overlap, rv);
        }
        return rv;
    }
}
Maximum White Tiles Covered by a Carpet LeetCode Solution Review:

In our experience, we suggest you solve this Maximum White Tiles Covered by a Carpet and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Maximum White Tiles Covered by a Carpet LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Maximum White Tiles Covered by a Carpet LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.