How does binary search apply to the "Fruits Into Baskets II" problem?

Binary search is used to narrow down the range of fruit types that can be placed into baskets, optimizing the process.

What is the optimal way to simulate fruit placement in this problem?

The optimal way is to iterate through the baskets, placing fruits while tracking how many types remain unplaced.

What happens if no fruit types can be placed in baskets?

If no fruits can be placed, the solution will return the total number of fruit types as unplaced.

How does GhostInterview help with the binary search optimization?

GhostInterview assists by providing hints and structured feedback on how to approach the binary search effectively for this problem.

Can the "Fruits Into Baskets II" problem be solved with a greedy approach?

A greedy approach is not ideal for this problem, as it requires a more refined search method to efficiently place fruits into baskets.

#3477

Easy

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

水果成篮 II

给你两个长度为 n 的整数数组， fruits 和 baskets ，其中 fruits[i] 表示第 i 种水果的数量， baskets[j] 表示第 j 个篮子的容量。你需要对 fruits 数组从左到右按照以下规则放置水果：每种水果必须放入第一个容量大于等于该水果数量的最左侧…

数组二分查找线段树模拟有序集合

题目描述

给你两个长度为 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 <= 100
1 <= fruits[i], baskets[i] <= 1000

lightbulb

解题思路

方法一：模拟

我们用一个长度为 $n$ 的布尔数组 $\textit{vis}$ 记录已经被使用的篮子，用一个答案变量 $\textit{ans}$ 记录所有未被放置的水果，初始时 $\textit{ans} = n$ 。

接下来，我们遍历每一种水果 $x$ ，对于当前水果，我们遍历所有的篮子，找出第一个未被使用，且容量大于等于 $x$ 的篮子 $i$ 。如果找到了，那么答案 $\textit{ans}$ 减 $1$ 。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{fruits}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(fruits)
        vis = [False] * n
        ans = n
        for x in fruits:
            for i, y in enumerate(baskets):
                if y >= x and not vis[i]:
                    vis[i] = True
                    ans -= 1
                    break
        return ans

speed

复杂度分析

指标	值
时间	O(n^2)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain how binary search helps in narrowing down the valid answer space?
question_mark
Does the candidate simulate the allocation process clearly and efficiently?
question_mark
Is the candidate aware of optimizations like early stopping to avoid unnecessary checks?

warning

常见陷阱

外企场景

error
Misunderstanding the problem statement and returning the wrong number of unplaced fruits.
error
Overcomplicating the binary search logic without focusing on the correct range.
error
Failing to optimize the simulation step, leading to excessive computation time.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the number of baskets exceeds the number of fruit types? How does the solution scale?
arrow_right_alt
Can this problem be adapted to handle varying basket types or additional constraints?
arrow_right_alt
How would the solution change if we needed to track which fruits were unplaced, instead of just counting them?

help

常见问题

外企场景

继续练习

#3479 水果成篮 III #2659 将数组清空 #3454 分割正方形 II