2271. 毯子覆盖的最多白色砖块数 ●●

2271. 毯子覆盖的最多白色砖块数 ●●

描述

给你一个二维整数数组 tiles ，其中 $tiles[i]=[l_i,r_i]$ ，表示所有在 $l_i<=j<=r_i$ 之间的每个瓷砖位置 j 都被涂成了白色。

同时给你一个整数 carpetLen ，表示可以放在 任何位置 的一块毯子。

请你返回使用这块毯子，最多 可以盖住多少块瓷砖。

示例

输入：tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
输出：9
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 9 块瓷砖，所以返回 9 。
注意可能有其他方案也可以覆盖 9 块瓷砖。
可以看出，瓷砖无法覆盖超过 9 块瓷砖。

题解

1. 双指针 + 滑动窗口

核心思路：滑动窗口，右指针不断扩大，直到不能继续后移（该段不是完全被覆盖的情况），收缩左指针，让右指针再次尝试扩大。

毯子覆盖情况：

1. 完全覆盖当前 right 段，则记录长度，右指针右移，计算更多覆盖的长度；
2. 覆盖部分 right 段，记录长度，毯子（左指针）右移；
3. 完全不覆盖当前 right 段，毯子（左指针）右移。

---

• 时间复杂度：$O(n\log n)$，其中 n 为 tiles 的长度。对 tiles 数组排序的时间复杂度为 $O(n\log n)$，双指针维护最多可覆盖数量的时间复杂度为 O(n)。
• 空间复杂度：$O(\log n)$，即为排序的栈空间开销。

class Solution {
    
public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
    
        sort(tiles.begin(), tiles.end(), [](vector<int>& a, vector<int>& b){
    
            return a[0] < b[0];                     // 开头升序排序
        });
        int n = tiles.size();
        int left = 0, right = 0, len = 0, ans = 0;
        while(left <= right && right < n){
    
            int rightMax = tiles[left][0] + carpetLen - 1;
            if(tiles[right][1] <= rightMax){
            // 整段覆盖
                len += tiles[right][1] - tiles[right][0] + 1;
                ans = max(ans, len);
                ++right;                            // 该段全部覆盖的情况下，才继续移动右指针，否则移动左指针
            }else{
                                      // 非整段覆盖：该段部分覆盖 / 该段完全不覆盖 
                if(tiles[right][0] <= rightMax){
        // 部分覆盖
                    ans = max(ans, len + rightMax - tiles[right][0] + 1);   // 因为接下来要移动左指针，因此直接比较当前部分覆盖情况下的最长长度
                    if(ans >= carpetLen) return carpetLen;
                }
                // 移动毯子起始位置到下一区间开头
                len -= tiles[left][1] - tiles[left][0] + 1;   
                ++left;       
            }
        } 
        return ans;
    }
};