---
# System prepended metadata

title: 2358. Maximum Number of Groups Entering a Competition
tags: [Leetcode, Sorting, Binary Search, Medium, Math, Greedy]

---

# 2358. Maximum Number of Groups Entering a Competition
###### tags: `Leetcode` `Medium` `Math` `Binary Search` `Greedy` `Sorting`
Link: https://leetcode.com/problems/maximum-number-of-groups-entering-a-competition/description/
## 思路
我们可以先把所有的grade排序 然后第一组放最小的一个 第二组放次小的两个 以此类推
我们令```n```是grades的长度
我们只要找到最小的整数```k``` ```1+2+3...+k>n``` 那么```k-1```就是答案
一种方法是我们可以用binary search找 最小的整数```k``` ```(1+k)*k/2>n```
另外一种数学方法
```1 + 2 + ... + k <= n```
```k(k + 1) / 2 <= n```
```(k + 0.5)(k + 0.5) <= n * 2 + 0.25```
```k + 0.5 <= sqrt(n * 2 + 0.25)```
```k <= sqrt(n * 2 + 0.25) - 0.5```
## Code
### Binary Search
```java=
class Solution {
    public int maximumGroups(int[] grades) {
        int n = grades.length;
        int start = 0, end = 1000; 
        while(start<end){
            int mid = start+(end-start)/2;
            if(mid*(mid+1)/2<=n) start = mid+1;
            else end = mid;
        }
        return start-1;
    }
}
```
### Math
```java=
class Solution {
    public int maximumGroups(int[] grades) {
        //k <= sqrt(n * 2 + 0.25) - 0.5
        return (int)(Math.sqrt(grades.length*2+0.25)-0.5);
    }
}
```
