<p>You are given a <strong>0-indexed</strong> array <code>usageLimits</code> of length <code>n</code>.</p>

<p>Your task is to create <strong>groups</strong> 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 <strong>across all groups</strong>. You must also satisfy the following conditions:</p>

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

<p>Return <em>an integer denoting the <strong>maximum</strong> number of groups you can create while satisfying these conditions.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> <code>usageLimits</code> = [1,2,5]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> <code>usageLimits</code> = [2,1,2]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> <code>usageLimits</code> = [1,1]
<strong>Output:</strong> 1
<strong>Explanation:</strong> 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>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= usageLimits.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= usageLimits[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        # First, the maximum possible groups is n because group length must be strictly increasing. So the best case is 1,2,...,n.
        # Second, the usage limit means we can use up to (but can be less than) the limit of each numbers.
        # Apporach 2: binary search
        # We sort the usage limit reversely and try to construct a triangle with length k.
        # We start with the usage with the most limit. If the current limit < required limit, then we pick all the current limit and store the current deficit. The deficit can be compensated with the numbers with less usage limit (we cannot do the reverse because it will cause duplicated element in a group). If the current limit > required limit, then we pick the occurrences of the required limit, and try to fill the deficit with the remaining occurrences.
        # If the deficit can be filled up after traversing all the usage limits, then it is possible to form such a group. Otherwise it is impossible.
        usageLimits.sort(reverse=True)

        def helper(k):
            deficit = 0
            for limit in usageLimits:
                if limit > k:
                    if deficit < 0:
                        deficit = min(0, deficit + limit - k)
                elif limit < k:
                    deficit += (limit - k)
                k = max(k - 1, 0)
                if k == 0 and deficit == 0:
                    return True
            return deficit == 0

        lo, hi = 1, len(usageLimits)
        while lo < hi:
            mid = (lo + hi + 1) >> 1
            if helper(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo 
31200