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; } };
|