双周赛T3.毯子覆盖的最多白色砖块数

题目链接

贪心算法

提示：

1 <= tiles.length <= 5 * 104
tiles[i].length == 2
1 <= li <= ri <= 109
1 <= carpetLen <= 109
tiles 互相 不会重叠 。

看到这个提示，肯定是从tiles这边考虑

毯子一定是从某一块区域的端点开始铺的，所以遍历从每一块区域左端点开始

首先要找到能覆盖到的最右的区域

有四种情况

①毯子只能覆盖一块区域，能覆盖全

②毯子只能覆盖一块区域，不能覆盖全

③毯子能覆盖多块区域，最右边一块能覆盖到

④毯子能覆盖多块区域，最右边一块不能覆盖到

维护左边界和右边界，同时在计算完最后一块覆盖面积，如果只覆盖了部分，不要加到sum中，否则在左端点左移时会出现重复计数

class Solution {
    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        Arrays.sort(tiles, (a, b) -> {
            return a[0] - b[0];
        });
        int max = 0, sum = 0, n = tiles.length, l = 0, r = 0;
        while (r < n) {
            int leftBoundary = tiles[l][0], rightBoundary = leftBoundary + carpetLen - 1;
            if (tiles[r][1] <= rightBoundary) {
                sum += tiles[r][1] - tiles[r][0] + 1;
                r++;
                max = Math.max(sum, max);
            } else {
                if (tiles[r][0] <= rightBoundary) {
                    max = Math.max(max, sum + rightBoundary - tiles[r][0] + 1);
                }
                sum -= tiles[l][1] - tiles[l][0] + 1;
                l++;
            }
        }
        return max;
    }
}