fruits-into-baskets-ii

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two arrays of integers, <code>fruits</code> and <code>baskets</code>, each of length <code>n</code>, where <code>fruits[i]</code> represents the quantity of the <code>ith</code> type of fruit, and <code>baskets[j]</code> represents the capacity of the <code>jth</code> basket.

From left to right, place the fruits according to these rules:

<ul>
	<li>Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.</li>
	<li>Each basket can hold only one type of fruit.</li>
	<li>If a fruit type cannot be placed in any basket, it remains unplaced.</li>
</ul>

Return the number of fruit types that remain unplaced after all possible allocations are made.

&nbsp;
Example 1:

<div class="example-block">
Input: fruits = [4,2,5], baskets = [3,5,4]

Output: 1

Explanation:

<ul>
	<li><code>fruits[0] = 4</code> is placed in <code>baskets[1] = 5</code>.</li>
	<li><code>fruits[1] = 2</code> is placed in <code>baskets[0] = 3</code>.</li>
	<li><code>fruits[2] = 5</code> cannot be placed in <code>baskets[2] = 4</code>.</li>
</ul>

Since one fruit type remains unplaced, we return 1.
</div>

Example 2:

<div class="example-block">
Input: fruits = [3,6,1], baskets = [6,4,7]

Output: 0

Explanation:

<ul>
	<li><code>fruits[0] = 3</code> is placed in <code>baskets[0] = 6</code>.</li>
	<li><code>fruits[1] = 6</code> cannot be placed in <code>baskets[1] = 4</code> (insufficient capacity) but can be placed in the next available basket, <code>baskets[2] = 7</code>.</li>
	<li><code>fruits[2] = 1</code> is placed in <code>baskets[1] = 4</code>.</li>
</ul>

Since all fruits are successfully placed, we return 0.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>n == fruits.length == baskets.length</code></li>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= fruits[i], baskets[i] &lt;= 1000</code></li>
</ul>

numOfUnplacedFruits

Fruits Into Baskets II

Fruit Into Baskets

fruit-into-baskets

水果成篮

Segment Tree

Array

Binary Search

Simulation

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

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

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

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

&nbsp;

示例 1

<div class="example-block">
输入： fruits = [4,2,5], baskets = [3,5,4]

输出： 1

解释：

<ul>
	<li><code>fruits[0] = 4</code> 放入 <code>baskets[1] = 5</code>。</li>
	<li><code>fruits[1] = 2</code> 放入 <code>baskets[0] = 3</code>。</li>
	<li><code>fruits[2] = 5</code> 无法放入 <code>baskets[2] = 4</code>。</li>
</ul>

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

示例 2

<div class="example-block">
输入： fruits = [3,6,1], baskets = [6,4,7]

输出： 0

解释：

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

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

&nbsp;

提示：

<ul>
	<li><code>n == fruits.length == baskets.length</code></li>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= fruits[i], baskets[i] &lt;= 1000</code></li>
</ul>