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

标签: 贪心 数组 二分查找 前缀和 排序

难度: Medium

给你一个二维整数数组 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 * 104
  • tiles[i].length == 2
  • 1 <= li <= ri <= 109
  • 1 <= carpetLen <= 109
  • tiles 互相 不会重叠 。

Submission

运行时间: 139 ms

内存: 35.7 MB

class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        if not tiles:
            return 0
        tiles.sort(key=lambda x: x[0])

        n = len(tiles)
        ans = 0
        cnt = 0
        r = 0
        for l in range(n):
            if l:
                cnt -= tiles[l-1][1] - tiles[l-1][0] + 1
            while r < n and tiles[l][0] + carpetLen > tiles[r][1]:
                cnt += tiles[r][1] - tiles[r][0] + 1
                r += 1
            if r == n:
                ans = max(ans, cnt)
                return ans
            extra = max(0, tiles[l][0] + carpetLen - tiles[r][0])
            ans = max(ans, cnt + extra)
            
        return ans

Explain

这个问题可以通过排序和滑动窗口技术来解决。首先，将瓷砖按照起始位置排序。定义两个指针l和r，表示当前正在考虑的瓷砖范围。变量cnt用于记录当前窗口内瓷砖的总数。从左到右遍历瓷砖，每次移动左指针l，减去左边瓷砖的数量，并尝试向右扩展右指针r，直到毯子的右边界超过了r指针指向的瓷砖的右端。每次右移r时，更新cnt以包括新增的瓷砖。如果毯子的右边界落在r指向的瓷砖内部，计算并更新可能的额外覆盖数量。最终，ans记录了所有可能情况下的最大覆盖数。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        if not tiles:
            return 0
        # 对瓷砖按起始位置进行排序
        tiles.sort(key=lambda x: x[0])

        n = len(tiles)
        ans = 0
        cnt = 0
        r = 0
        # 使用滑动窗口遍历瓷砖
        for l in range(n):
            # 更新窗口左边界，减去移出窗口的瓷砖数量
            if l:
                cnt -= tiles[l-1][1] - tiles[l-1][0] + 1
            # 尝试扩展右边界
            while r < n and tiles[l][0] + carpetLen > tiles[r][1]:
                cnt += tiles[r][1] - tiles[r][0] + 1
                r += 1
            # 如果已经无法扩展右边界，直接返回当前最大值
            if r == n:
                ans = max(ans, cnt)
                return ans
            # 计算额外覆盖的瓷砖数量
            extra = max(0, tiles[l][0] + carpetLen - tiles[r][0])
            # 更新最大覆盖瓷砖数
            ans = max(ans, cnt + extra)
            
        return ans

Explore

对瓷砖按起始位置进行排序是为了使瓷砖的位置信息变得有序，便于通过滑动窗口方法进行有效的遍历和计算。排序后，我们可以确保在遍历时，每一个瓷砖的起始位置都不会比前一个小，这样可以在扩展或收缩窗口时简化计算逻辑，避免重复考虑或遗漏瓷砖。此外，排序还有助于快速判断毯子是否可以覆盖连续区域，以及在达到毯子长度限制时优化查找和计算过程。

在滑动窗口技术中，指针r向右扩展的目的是尝试包含更多的瓷砖，以增加当前窗口内的瓷砖总数。指针r会继续向右移动，直到毯子的右边界超过了r指向的瓷砖的右端。具体地，当毯子的右边界（即从当前左指针l开始的毯子长度范围内）还在下一个瓷砖的结束位置之内时，r指针会继续向右移动，并将新覆盖的瓷砖数量加入到cnt变量中。r指针停止移动的条件是当毯子的右边界超出了当前r指向的瓷砖的结束位置，或者r指针已经达到瓷砖列表的末尾。

在计算额外覆盖的瓷砖数量时，使用`max(0, tiles[l][0] + carpetLen - tiles[r][0])`是为了计算毯子可能从r指向的瓷砖开始位置覆盖的额外长度，而不直接考虑瓷砖的结束位置`tiles[r][1]`，是因为毯子可能不会完全覆盖到r指向的瓷砖的末尾。这个计算考虑的是毯子从r瓷砖的起始位置开始可能覆盖的最大长度，但不超过瓷砖本身的长度。通过这种方式，可以确保不会过度计算覆盖长度，同时也简化了计算过程。当计算出的值为负数时，使用`max(0, ...)`确保不会添加无效的覆盖长度。