LeetCode 2271. Maximum White Tiles Covered by a Carpet

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        Arrays.sort(tiles, (a, b) -> a[0] - b[0]);
        int n = tiles.length, ans = 0;
        for (int l = 0, r = 0, s = 0; r < n; ++l) {
            while (r < n && tiles[r][1] - tiles[l][0] + 1 <= carpetLen) {
                s += tiles[r][1] - tiles[r][0] + 1;
                ++r;
            }
            if (r == n) ans = Math.max(ans, s);
            else {
                int coveredPath = Math.max(tiles[l][0] + carpetLen - tiles[r][0], 0);
                ans = Math.max(ans, coveredPath + s);
                s -= tiles[l][1] - tiles[l][0] + 1;
            }
        }
        return ans;
    }
}
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(int[][] tiles, int carpetLen) {
        Arrays.sort(tiles, (a, b) -> a[0] - b[0]);
        int n = tiles.length, ans = 0;
        for (int l = 0, r = 0, s = 0; r < n;) {
            int leftBoundary = tiles[l][0], rightBoundary = leftBoundary + carpetLen - 1;
            if (tiles[r][1] <= rightBoundary) { // covered.
                s += tiles[r][1] - tiles[r][0] + 1;
                ans = Math.max(ans, s);
                ++r;
            } else {
                if (rightBoundary > tiles[r][0]) // partially covered.
                    ans = Math.max(ans, s + rightBoundary - tiles[r][0] + 1);
                s -= tiles[l][1] - tiles[l][0] + 1;
                ++l;
            }
        }
        return ans;
    }
}