Leetcode 2271. Maximum White Tiles Covered by a Carpet

[Woodyiiiiiii]

这道题是双周赛第三题。

看完题目，要知道关键的两点：

1. 为了尽量满足cover更多的white tiles，carpet要从每个区间的左起点开始往右cover，而不用考虑从区间的右节点往左cover。
2. 为了时间复杂度，而且还是一个区间在另一个区间移动的问题，使用**sliding window(滑动窗口)**方法。

我做的时候两点都没想明白

class Solution {
    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        
        long res = 0;
        // sort
        Arrays.sort(tiles, Comparator.comparingInt(a -> a[0]));

        long sq = 0;
        int l = 0;
        int r = 0;
        int n = tiles.length;
        while (r < n && l < n) {
            if (tiles[l][0] + carpetLen - 1 > tiles[r][1]) {
                sq += (tiles[r][1] - tiles[r][0] + 1);
                res = Math.max(res, sq);
                ++r;
            } else {
                if (tiles[l][0] + carpetLen - 1 >= tiles[r][0]) {
                    res = Math.max(res, sq + (tiles[l][0] + carpetLen - tiles[r][0]));
                }
                if (tiles[l][0] + carpetLen - 1 > tiles[l][1]) {
                    sq -= (tiles[l][1] - tiles[l][0] + 1);
                } else {
                    sq -= (carpetLen);
                }
                ++l;
                r = Math.max(r, l);
            }
        }

        return (int)res;
        
    }
}

---

参考资料：

• https://leetcode.com/problems/maximum-white-tiles-covered-by-a-carpet/
• https://leetcode.com/problems/maximum-white-tiles-covered-by-a-carpet/discuss/2038534/Sliding-Window