【暴力】毯子覆盖的最多白色砖块数

题目

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

---

给你一个二维整数数组 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 。

提示：

• 1 <= tiles.length <= 5 * 10^4
• tiles[i].length == 2
• 1 <= li <= ri <= 10^9
• 1 <= carpetLen <= 10^9
• tiles 互相 不会重叠 。

解题

方法一：暴力

思路

计算出白色砖块的总数(total)，把所有砖块按照砖块的开始位置进行排序，记排序后第一部分砖块的开始为 minStart，最后一部分砖块的结束为 maxEnd，tiles 互相 不会重叠，所以 maxEnd 一定是最后一块砖块，所以只要 maxEnd - maxStart + 1 长度的毯子就可以盖住所有砖块。

如果毯子不能盖住所有砖块，就遍历所有部分的砖块：

• 记 bound = tiles[i][0] + carpetLen 表示此时毯子从 tiles[i][0] (包含)开始能盖到 bound (不包含)。
• 如果 bound 超过了 maxEnd + 1 则一定有一部分的毯子会浪费，略过这种情况。
• 记 curr 表示当前这种情况下毯子能盖到的白色砖块数，从当前部分砖块开始向后遍历：
  • 如果部分砖块的起始大于等于 bound，说明毯子已经接触不到这部分砖块了，直接 break。
  • 如果部分砖块的结束小于 bound，直接把这部分砖块的长度加入毯子能覆盖到的部分。
  • 否则如果部分砖块的起始小于 bound ，把这部分砖块的起始到 bound 部分加入毯子能覆盖到的部分。
• 从所有情况中取毯子所能覆盖到最长的部分的长度。

代码

class Solution {
    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        int len = tiles.length;
        int total = 0;
        for (int i = 0; i < len; i++) {
            total += tiles[i][1] - tiles[i][0] + 1;
        }
        Arrays.sort(tiles, (a, b) -> a[0] - b[0]);
        int minStart = tiles[0][0], maxEnd = tiles[len - 1][1];
        if (carpetLen >= maxEnd - minStart + 1) return total;
        int max = 0;
        for (int i = 0; i < len; i++) {
            int bound = tiles[i][0] + carpetLen;
            if (bound > maxEnd + 1) break;
            int curr = 0;
            for (int j = i; j < len; j++) {
                if (tiles[j][0] >= bound) break;
                if (tiles[j][1] < bound) {
                    curr += tiles[j][1] - tiles[j][0] + 1;
                } else if (tiles[j][0] < bound) {
                    curr += bound - tiles[j][0];
                }
            }
            max = Math.max(max, curr);
        }
        return max;
    }
}