# 2271. Maximum White Tiles Covered by a Carpet
###### tags: `Leetcode` `Medium` `Greedy` `Sliding Window`
Link: https://leetcode.com/problems/maximum-white-tiles-covered-by-a-carpet/
## 思路
greedy的地方在于 carpet的leftEnd跟每一个white tile的起点对齐才能找到最佳解 因为如果往右挪 左边一定会少一个 右边不知道会不会多一个

逐一考察毯子的左边界应该对齐哪个```tile```的左边界即可，在这个过程中，毯子的右边界的位置自然也是单调递增的，所以本题就是维护一个双指针的滑窗

假设毯子的左边界对应的是```tiles[i][0]```，那么我们向右移动指针```j```来定位毯子右边界解出的是哪个```tile```，直至```tiles[i][0]+carpetLen-1 < tiles[j][1]``` 如图

carpet ____________________________
 tiles _____  ________ ________  _______
         i                           j

此时```tiles[i: j-1]```这部分的瓷砖是完全被覆盖的，我们可以用前缀和之差来计算这些```tiles```的瓷砖总数。另外我们需要计算第```j```个```tile```被额外覆盖了多少，这也容易得到：```tiles[i][0]+carpetLen-1-tiles[j][0]+1```. 两部分相加就是地毯在这个位置的覆盖面积

随着地毯移动```n```次，取全局的最大值即可
## Code

class Solution {
    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        int n = tiles.length;
        Arrays.sort(tiles, (a,b)->(a[0]-b[0]));
        int[] prefix = new int[n];
        int curr = 0;
        for(int i=0; i<n; i++){
            curr += tiles[i][1]-tiles[i][0]+1;
            prefix[i] = curr;
        }
        int ans = 0;
        int j=0;
        for(int i=0; i<n; i++){
            while(j<n && tiles[i][0]+carpetLen>tiles[j][1]){
                j++;
            }
            int len = 0;
            if(j==i) len = carpetLen;
            else{
                len = prefix[j-1]-(i==0?0:prefix[i-1]);
                if(j!=n) len += Math.max(0,tiles[i][0]+carpetLen-1-tiles[j][0]+1);
            }
            ans = Math.max(ans, len);
        }
        return ans;
    }
}