[LeetCode] Maximum White Tiles Covered by a Carpet

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int maximumWhiteTiles(vector<vector<int>>& tiles, int clen) {
sort(begin(tiles), end(tiles));
vector<int> space{0};
int res = 0, n = tiles.size();
for(int i = 1; i < n; i++) {
space.push_back(space.back() + tiles[i][0] - tiles[i-1][1] - 1);
}
int l = 0, r = 0;
while(r < n) {
while(r < n and tiles[l][0] + clen > tiles[r][0]) {r++;}
res = max(res,
min(tiles[l][0] + clen - 1, tiles[r-1][1]) - tiles[l][0] - (space[r-1] - space[l]) + 1
);
l++;
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/15/PS/LeetCode/maximum-white-tiles-covered-by-a-carpet/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.