侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-05-15 / 0 评论 / 0 点赞 / 34 阅读 / 791 字 / 正在检测是否收录...

题目

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


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

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

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

示例 1:

image-20220623114535358

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

示例 2:

image-20220623114540378

输入: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,最后一部分砖块的结束为 maxEndtiles 互相 不会重叠,所以 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;
    }
}
0

评论区