minimum-number-of-groups-to-create-a-valid-assignment

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given a collection of numbered <code>balls</code>&nbsp;and instructed to sort them into boxes for a nearly balanced distribution. There are two rules you must follow:

<ul>
	<li>Balls with the same&nbsp;box must have the same value. But, if you have more than one ball with the same number, you can put them in different boxes.</li>
	<li>The biggest box can only have one more ball than the smallest box.</li>
</ul>

​Return the fewest number of boxes to sort these balls following these rules.

&nbsp;
Example 1: 

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
Input: balls = [3,2,3,2,3] 

Output: 2 

Explanation:

We can sort <code>balls</code> into boxes as follows:

<ul>
	<li><code>[3,3,3]</code></li>
	<li><code>[2,2]</code></li>
</ul>

The size difference between the two boxes doesn&#39;t exceed one.
</div>

Example 2: 

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
Input: balls = [10,10,10,3,1,1] 

Output: 4 

Explanation:

We can sort <code>balls</code> into boxes as follows:

<ul>
</ul>

<ul>
	<li><code>[10]</code></li>
	<li><code>[10,10]</code></li>
	<li><code>[3]</code></li>
	<li><code>[1,1]</code></li>
</ul>

You can&#39;t use fewer than four boxes while still following the rules. For example, putting all three balls numbered 10 in one box would break the rule about the maximum size difference between boxes.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>

第 368 场周赛

weekly-contest-368

minGroupsForValidAssignment

资深工程师

Minimum Number of Groups to Create a Valid Assignment

Greedy

Array

Hash Table

给你一组带编号的&nbsp;<code>balls</code> 并要求将它们分类到盒子里，以便均衡地分配。你必须遵守两条规则：

<ul>
	<li>同一个盒子里的球必须具有相同的编号。但是，如果你有多个相同编号的球，你可以把它们放在不同的盒子里。</li>
	<li>最大的盒子只能比最小的盒子多一个球。</li>
</ul>

返回遵循上述规则排列这些球所需要的盒子的最小数目。

&nbsp;

示例 1：

<pre>
输入：balls = [3,2,3,2,3]
输出：2
解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：
我们可以如下排列 balls 到盒子里：
- [3,3,3]
- [2,2]
两个盒子之间的大小差没有超过 1。</pre>

示例 2：

<pre>
输入：balls = [10,10,10,3,1,1]
输出：4
解释：我们可以如下排列 balls 到盒子里：
- [10]
- [10,10]
- [3]
- [1,1]
无法得到一个遵循上述规则且小于 4 盒的答案。例如，把所有三个编号为 10 的球都放在一个盒子里，就会打破盒子之间最大尺寸差异的规则。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= balls.length &lt;= 105</code></li>
	<li><code>1 &lt;= balls[i] &lt;= 109</code></li>
</ul>