2271. Maximum number of white bricks covered by blanket ●●

2271. The maximum number of white bricks covered by the blanket ●●

describe

Here's a two-dimensional array of integers tiles , among $tiles[i]=[l_i,r_i]$ , All in $l_i<=j<=r_i$ Each tile location between j All painted white .

I'll give you an integer at the same time carpetLen , Can be placed in Any location A blanket .

Please return to this blanket , most Sure How many tiles are covered .

Example

Input ：tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
Output ：9
explain ： Remove the blanket from the tile 10 Start placing .
Total coverage 9 A tile , So back 9 .
Note that there may be other schemes that can also cover 9 A tile .
It can be seen that , Tiles cannot cover more than 9 A tile .

Answer key

1. Double pointer + The sliding window

The core idea ： The sliding window , The right pointer keeps expanding , Until you can't move back （ This paragraph is not completely covered ）, Shrink the left pointer , Let the right pointer try to expand again .

Blanket coverage ：

1. Completely overwrite the current right paragraph , Record length , Right pointer moves right , Calculate the length of more coverage ;
2. Covering part right paragraph , Record length , Blanket （ Left pointer ） Move right ;
3. Do not overwrite the current right paragraph , Blanket （ Left pointer ） Move right .

---

• Time complexity ：$O(n\log n)$, among n by tiles The length of . Yes tiles The time complexity of array sorting is $O(n\log n)$, The maximum time complexity of double pointer maintenance is O(n).
• Spatial complexity ：$O(\log n)$, That is, the stack space overhead of sorting .

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];                     //  Sort in ascending order at the beginning 
        });
        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){
            //  Whole segment coverage 
                len += tiles[right][1] - tiles[right][0] + 1;
                ans = max(ans, len);
                ++right;                            //  When this section is completely covered , Then continue to move the right pointer , Otherwise, move the left pointer 
            }else{
                                      //  Incomplete segment coverage ： This section partially covers  /  This paragraph does not cover  
                if(tiles[right][0] <= rightMax){
        //  Partial coverage 
                    ans = max(ans, len + rightMax - tiles[right][0] + 1);   //  Because next, you have to move the left pointer , Therefore, directly compare the longest length under the current partial coverage 
                    if(ans >= carpetLen) return carpetLen;
                }
                //  Move the starting position of the blanket to the beginning of the next interval 
                len -= tiles[left][1] - tiles[left][0] + 1;   
                ++left;       
            }
        } 
        return ans;
    }
};