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

思路：

贪心+滑动窗口。

实现：

 1 class Solution {
 2 public:
 3     static bool cmp(vector<int>&a,vector<int>&b){
 4         if(a[0]!=b[0]){
 5             return a[0]0];
 6         }
 7         return a[1]1];
 8     }
 9     int get_len(vector<int>&t){
10         return t[1]-t[0]+1;
11     }
12     int maximumWhiteTiles(vectorint>>& tiles, int carpetLen) {
13         sort(tiles.begin(),tiles.end(),cmp);
14         int n=tiles.size();
15         int slow=0,sum=0;
16         int res=0;
17         for(int i=0;i){
18             int len=get_len(tiles[i]);
19             sum+=len;
20             while(slow0]+carpetLen-10]){
21                 sum-=get_len(tiles[slow]);
22                 slow++;
23             }
24             int end=tiles[slow][0]+carpetLen-1;
25             if(end>=tiles[i][1]){
26                 res=max(res,sum);
27             }
28             else{
29                 while(slow1]){
30                     int tmp=sum-len+end-tiles[i][0]+1;
31                     res=max(res,tmp);
32                     sum-=get_len(tiles[slow]);
33                     slow++;
34                     end=tiles[slow][0]+carpetLen-1;
35                 }
36                 if(slow<i){
37                     res=max(res,sum);
38                 }
39                 else{
40                     res=max(res,min(get_len(tiles[i]),carpetLen));
41                 }
42             }
43         }
44         return res;
45     }
46 };