maximum-number-of-groups-with-increasing-length

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 a 0-indexed array <code>usageLimits</code> of length <code>n</code>.

Your task is to create groups using numbers from <code>0</code> to <code>n - 1</code>, ensuring that each number, <code>i</code>, is used no more than <code>usageLimits[i]</code> times in total across all groups. You must also satisfy the following conditions:

<ul>
	<li>Each group must consist of distinct numbers, meaning that no duplicate numbers are allowed within a single group.</li>
	<li>Each group (except the first one) must have a length strictly greater than the previous group.</li>
</ul>

Return an integer denoting the maximum number of groups you can create while satisfying these conditions.

&nbsp;
Example 1:

<pre>
Input: <code>usageLimits</code> = [1,2,5]
Output: 3
Explanation: In this example, we can use 0 at most once, 1 at most twice, and 2 at most five times.
One way of creating the maximum number of groups while satisfying the conditions is: 
Group 1 contains the number [2].
Group 2 contains the numbers [1,2].
Group 3 contains the numbers [0,1,2]. 
It can be shown that the maximum number of groups is 3. 
So, the output is 3. </pre>

Example 2:

<pre>
Input: <code>usageLimits</code> = [2,1,2]
Output: 2
Explanation: In this example, we can use 0 at most twice, 1 at most once, and 2 at most twice.
One way of creating the maximum number of groups while satisfying the conditions is:
Group 1 contains the number [0].
Group 2 contains the numbers [1,2].
It can be shown that the maximum number of groups is 2.
So, the output is 2. 
</pre>

Example 3:

<pre>
Input: <code>usageLimits</code> = [1,1]
Output: 1
Explanation: In this example, we can use both 0 and 1 at most once.
One way of creating the maximum number of groups while satisfying the conditions is:
Group 1 contains the number [0].
It can be shown that the maximum number of groups is 1.
So, the output is 1. 
</pre>

&nbsp;
Constraints:

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

maxIncreasingGroups

Maximum Number of Groups With Increasing Length

Group the People Given the Group Size They Belong To

group-the-people-given-the-group-size-they-belong-to

用户分组

Greedy

Array

Math

Binary Search

Sorting

给你一个下标从 0 开始、长度为 <code>n</code> 的数组 <code>usageLimits</code> 。

你的任务是使用从 <code>0</code> 到 <code>n - 1</code> 的数字创建若干组，并确保每个数字 <code>i</code> 在 所有组 中使用的次数总共不超过 <code>usageLimits[i]</code> 次。此外，还必须满足以下条件：

<ul>
	<li>每个组必须由 不同 的数字组成，也就是说，单个组内不能存在重复的数字。</li>
	<li>每个组（除了第一个）的长度必须 严格大于 前一个组。</li>
</ul>

在满足所有条件的情况下，以整数形式返回可以创建的最大组数。

&nbsp;

示例 1：

<pre>
<code>输入：usageLimits</code> = [1,2,5]
输出：3
解释：在这个示例中，我们可以使用 0 至多一次，使用 1 至多 2 次，使用 2 至多 5 次。
一种既能满足所有条件，又能创建最多组的方式是： 
组 1 包含数字 [2] 。
组 2 包含数字 [1,2] 。
组 3 包含数字 [0,1,2] 。 
可以证明能够创建的最大组数是 3 。 
所以，输出是 3 。 </pre>

示例 2：

<pre>
<code>输入：</code><code>usageLimits</code> = [2,1,2]
输出：2
解释：在这个示例中，我们可以使用 0 至多 2 次，使用 1 至多 1 次，使用 2 至多 2 次。
一种既能满足所有条件，又能创建最多组的方式是： 
组 1 包含数字 [0] 。 
组 2 包含数字 [1,2] 。
可以证明能够创建的最大组数是 2 。 
所以，输出是 2 。 
</pre>

示例 3：

<pre>
<code>输入：</code><code>usageLimits</code> = [1,1]
输出：1
解释：在这个示例中，我们可以使用 0 和 1 至多 1 次。 
一种既能满足所有条件，又能创建最多组的方式是：
组 1 包含数字 [0] 。
可以证明能够创建的最大组数是 1 。 
所以，输出是 1 。 
</pre>

&nbsp;

提示：

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