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

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

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

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

链接：https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet

思路

滑动窗口+排序
前缀和+二分+排序

代码

class Solution {
public:
    int maximumWhiteTiles(vector>& tiles, int carpetLen) {
    
        sort(tiles.begin(),tiles.end());

        vector presum(tiles.size(),0);        // 前缀和数组
        vector arr(tiles.size(),0);
        int n=tiles.size();


        for(int i=0;i
            presum[i]=(tiles[i][1]-tiles[i][0]+1);
            arr[i]=tiles[i][1];
        }

        for(int i=1;i
            presum[i]+=presum[i-1];
        }

        int ans=0;
        int cnt;
        int j;
        for(int i=0;i
            int r=tiles[i][0]+carpetLen-1;
            auto iter=lower_bound(arr.begin(),arr.end(),r);
            if(iter!=arr.end())
            j=iter-arr.begin();
            else
            j=n;

            cnt=(j-1>=0?presum[j-1]:0)-(i-1>=0?presum[i-1]:0);

            if(j=tiles[j][0])
            cnt+=(r-tiles[j][0]+1);

            ans=max(ans,cnt);

        }

        return ans;
        
    }
};