304 North Cardinal St.
Dorchester Center, MA 02124

# 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] + len > t[i]) {
cover += t[i] - t[i] + 1;
res = max(res, cover);
++i;
}
else {
int partial = max(0, t[j] + len - t[i]);
res = max(res, cover + partial);
cover -= (t[j] - t[j] + 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)
# build the starting position array
startPos = [tiles[i] for i in range(len(tiles))]
# build the prefix sum array
preSum =  * (len(tiles) + 1)
for i in range(1, len(tiles) + 1):
preSum[i] = preSum[i - 1] + (tiles[i-1]-tiles[i-1] + 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] > s + carpetLen - 1:
compensate = tiles[endIdx] - 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));
int rv = 0, overlap = 0, ei = 0, prevEnd = 0;
for (int si = 0; si < tiles.length; si++) {
int st = tiles[si], end = st + carpetLen - 1;
if (si > 0) {
overlap -= (Math.min(prevEnd, tiles[si-1]) - tiles[si-1] + 1);
}
if (ei-1 >= si && tiles[ei-1] > prevEnd) {
overlap += (Math.min(end, tiles[ei-1]) - prevEnd);
}

while (ei < tiles.length && tiles[ei] <= end) {
overlap += (Math.min(end, tiles[ei]) - tiles[ei] + 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