2271. 毯子覆盖的最多白色砖块数-快速排序+滑动窗口，力扣双百代码

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

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

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

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

示例 1：

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

示例 2：

输入：tiles = [[10,11],[1,1]], carpetLen = 2
输出：2
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 2 块瓷砖，所以我们返回 2 。

解题代码如下：

void quick(int **a,int low,int high){
    if(low<high){
        int l=low,h=high,p1=a[low][0],p2=a[low][1];
        while(low<high){
            while(low<high&&a[high][0]>=p1){
                high--;
            }
            a[low][0]=a[high][0];
            a[low][1]=a[high][1];
            while(low<high&&a[low][0]<=p1){
                low++;
            }
             a[high][0]=a[low][0];
            a[high][1]=a[low][1];
        }
          a[low][0]=p1;
            a[low][1]=p2;
            quick(a,l,low-1);
            quick(a,low+1,h);
    }
}


int maximumWhiteTiles(int** tiles, int tilesSize, int* tilesColSize, int carpetLen){
    quick(tiles,0,tilesSize-1);
    int max=0;
    int low=0,high=0;
    int sum=0;
    // for(int i=0;i
    // printf("%d ",tiles[i][0]);
  
    while(low<tilesSize){
      
    
       
       while(tiles[high][1]-tiles[low][0]<carpetLen){
            sum=sum+tiles[high][1]-tiles[high][0]+1;
            if(sum>max){
                max=sum;
            }

               high++;  
                 if(high>=tilesSize){
                 break;
             } 
             

             }
                 if(high>=tilesSize){
                 break;
             }
              
              int sumx=sum+fmin(carpetLen+tiles[low][0]-tiles[high][0],tiles[high][1]-tiles[high][0]+1);

             if(sumx>max){
                max=sumx;
            }
           
            sum=sum-(tiles[low][1]-tiles[low][0]+1);
           
            low++;
           


    }
    return max;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68