2790-MaximumNumberOfGroupsWithIncreasingLength.go

package main

// 2790. Maximum Number of Groups With Increasing Length
// You are given a 0-indexed array usageLimits of length n.

// Your task is to create groups using numbers from 0 to n - 1, ensuring that each number, i, is used no more than usageLimits[i] times in total across all groups. 
// You must also satisfy the following conditions:
//     1. Each group must consist of distinct numbers, meaning that no duplicate numbers are allowed within a single group.
//     2. Each group (except the first one) must have a length strictly greater than the previous group.

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

// Example 1:
// Input: usageLimits = [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.

// Example 2:
// Input: usageLimits = [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. 

// Example 3:
// Input: usageLimits = [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. 

// Constraints:
//     1 <= usageLimits.length <= 10^5
//     1 <= usageLimits[i] <= 10^9

import "fmt"
import "sort"

func maxIncreasingGroups(usageLimits []int) int {
    sort.Ints(usageLimits)
    res, extra := 0, 0
    for i := 0; i < len(usageLimits); i++ {
        if extra + usageLimits[i] > res {
            res++
            needed := res
            if extra >= needed {
                extra += (usageLimits[i] - needed)
            } else {
                needed -= extra
                extra = usageLimits[i] - needed
            }
        } else {
            extra += usageLimits[i]
        }
    }
    return res
}

func maxIncreasingGroups1(usageLimits []int) int {
    sort.Ints(usageLimits)
    res, sum := 0, 0
    for _, v := range usageLimits {
        sum += v
        if sum > res {
            res++
            sum -= res
        }
    }
    return res
}

func main() {
    // Example 1:
    // Input: usageLimits = [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.
    fmt.Println(maxIncreasingGroups([]int{1,2,5})) // 3
    // Example 2:
    // Input: usageLimits = [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. 
    fmt.Println(maxIncreasingGroups([]int{2,1,2})) // 2
    // Example 3:
    // Input: usageLimits = [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. 
    fmt.Println(maxIncreasingGroups([]int{1,1})) // 1

    fmt.Println(maxIncreasingGroups([]int{1,2,3,4,5,6,7,8,9})) // 9
    fmt.Println(maxIncreasingGroups([]int{9,8,7,6,5,4,3,2,1})) // 9

    fmt.Println(maxIncreasingGroups1([]int{1,2,5})) // 3
    fmt.Println(maxIncreasingGroups1([]int{2,1,2})) // 2
    fmt.Println(maxIncreasingGroups1([]int{1,1})) // 1
    fmt.Println(maxIncreasingGroups1([]int{1,2,3,4,5,6,7,8,9})) // 9
    fmt.Println(maxIncreasingGroups1([]int{9,8,7,6,5,4,3,2,1})) // 9
}