3479.将水果放入篮子III

segment tree，https://leetcode.cn/problems/fruits-into-baskets-iii/

给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的数量，baskets[j] 表示第 j 个篮子的容量。

你需要对 fruits 数组从左到右按照以下规则放置水果：

每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
每个篮子只能装一种水果。
如果一种水果 无法放入 任何篮子，它将保持 未放置。

返回所有可能分配完成后，剩余未放置的水果种类的数量。

示例 1

输入： fruits = [4,2,5], baskets = [3,5,4]

输出： 1

解释：

fruits[0] = 4 放入 baskets[1] = 5。
fruits[1] = 2 放入 baskets[0] = 3。
fruits[2] = 5 无法放入 baskets[2] = 4。

由于有一种水果未放置，我们返回 1。

示例 2

输入： fruits = [3,6,1], baskets = [6,4,7]

输出： 0

解释：

fruits[0] = 3 放入 baskets[0] = 6。
fruits[1] = 6 无法放入 baskets[1] = 4（容量不足），但可以放入下一个可用的篮子 baskets[2] = 7。
fruits[2] = 1 放入 baskets[1] = 4。

由于所有水果都已成功放置，我们返回 0。

提示：

n == fruits.length == baskets.length
1 <= n <= 10^5
1 <= fruits[i], baskets[i] <= 10^9

基于线段树的解法，可以在 O(nlog⁡n)O(nlogn) 的时间内完成查询和更新操作，满足 n≤105n≤105 的要求。

代码说明

线段树构造： 用一个数组构造线段树，每个叶子节点对应一个篮子的容量，内部节点存储该区间的最大容量。
查询操作： 对于每个水果，利用线段树查询第一个（最左侧）可用且容量大于等于该水果数量的篮子。如果整个树的最大值都小于当前水果的数量，则该水果无法放置。
更新操作： 当一个篮子被使用后，将其容量更新为 0（因所有篮子容量均 ≥1）。

代码

python

from typing import List

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        class SegmentTree:
            def __init__(self, arr):
                self.n = len(arr)
                self.size = 1
                while self.size < self.n:
                    self.size *= 2

                # 构造一个大小为 2*size 的树，初始值均为 0
                self.tree = [0] * (2 * self.size)
                # 将原始数组填入叶子节点
                for i in range(self.n):
                    self.tree[self.size + i] = arr[i]
                # 从下往上构造内部节点：节点存储其两个子节点的最大值
                for i in range(self.size - 1, 0, -1):
                    self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1])

            def update(self, idx, value):
                """将索引 idx 处的值更新为 value，并更新所有祖先节点。"""
                i = idx + self.size
                self.tree[i] = value
                while i > 1:
                    i //= 2
                    self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1])

            def find_first_ge(self, x):
                """
                查找最左侧的篮子，其容量 >= x。
                如果不存在则返回 -1。
                """
                if self.tree[1] < x:
                    return -1
                i = 1
                while i < self.size:
                    if self.tree[2 * i] >= x:
                        i = 2 * i
                    else:
                        i = 2 * i + 1
                return i - self.size

        """
        对 fruits 中的每种水果，按照规则找出第一个可放置的篮子（左侧且容量满足条件）。
        每个篮子只能装一种水果，若无法找到，则记为未放置。
        返回未放置水果的种类数。
        """
        st = SegmentTree(baskets)
        unplaced = 0
        for fruit in fruits:
            idx = st.find_first_ge(fruit)
            if idx == -1:
                unplaced += 1
            else:
                # 使用该篮子，将其更新为0表示不可再用
                st.update(idx, 0)
        return unplaced

if __name__ == "__main__":
    sol = Solution()
    #print(sol.numOfUnplacedFruits([4,2,5], [3,5,4])) # 0
    #print(sol.numOfUnplacedFruits([3,6,1], [6,4,7]))
    #print(sol.numOfUnplacedFruits([8, 5], [1, 8]))# 1
    #print(sol.numOfUnplacedFruits([7,4,2,9,7], [5,2,6,7,7])) # 0
    print(sol.numOfUnplacedFruits([4,2,5], [3,5,4])) # 1

说明

对于每个水果，调用 find_first_ge 方法在 O(log⁡n)O(logn) 的时间内找到合适的篮子。
当找到篮子后，通过 update 方法将该篮子的容量置 0，从而使其后续不再被选用。
最后返回未放置水果的计数。

3479.将水果放入篮子III ​

3479.将水果放入篮子III