Поиск максимальных групп за меньшую временную сложность ⇐ JAVA

[Anonymous]

У меня есть массив размером n, array представляет количество элементов определенного типа, где i находится в диапазоне от 0 до n-1.
Я хочу упакуйте предметы в группы, следуя нижеприведенным правилам:

Код: Выделить всё

1. All items in a group should be distinct.
2. The current group size must be strictly greater than the group formed in previous batch.
3. Also each item can be grouped only once, and it is not required to group every item.
< /code>
Найдите максимальное количество групп, которые мы можем создать. Таким образом, количество элементов конкретного типа I (0 ≤I≤N-1) определяется массивом [i] < /p>
Example n=5
array = [2, 3, 1, 4,2]

An optimal way to create groups is:
1. The first group contains 1 item of item type 4. The remaining items = [2, 3, 1, 4, 1].
2. The second group contains 2 items of item types: 0 and 1. The remaining items = [1, 2, 1, 4, 1].
3. The third group contains 3 items of item types: 0, 1, and 3. The remaining items = [0, 1, 1, 3,1].
4. The fourth group contains 4 items of product types: 1, 2, 3, and 4. The remaining items = [0, 0, 0, 2, 0].

Наконец, у нас осталось 2 предмета, но для нашей следующей группы нужно 5 предметов разных типов (различных).
Поэтому можно подготовить только 4 группы, что является максимально возможным .
Я решил, используя приведенный ниже код:

Код: Выделить всё

import java.util.*;

public class Main {
public static int solve(List array) {
PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder());
for (int e : array) {
if (e > 0) maxHeap.offer(e);        }

int groups = 0;
int size = 1;
while (true) {
List tempList = new ArrayList();
int itemsAdded = 0;
while (!maxHeap.isEmpty() && itemsAdded < size) {
int count = maxHeap.poll();
itemsAdded++;
if (count > 1) {
tempList.add(count - 1);                }
}

if (itemsAdded < size) break;

for (int count : tempList) {
maxHeap.offer(count);
}

groups++;
size++;
}

return groups;
}

public static void main(String[] args) {
// Test cases
List ar1 = Arrays.asList(2, 3, 1, 4, 2);
System.out.println(solve(ar1)); // Output: 4

List ar2 = Arrays.asList(1, 2, 7);
System.out.println(solve(ar2)); // Output: 3

List ar3 = Arrays.asList(1, 2, 8, 9);
System.out.println(solve(ar3)); // Output: 4

List ar4 = Arrays.asList(12, 12, 11, 11, 8, 1, 1);
System.out.println(solve(ar4)); // Output: 6
}
}

Если размер ввода большой выше, код не удастся с ошибками времени, как решить это за меньшей сложности времени.

Подробнее здесь: https://stackoverflow.com/questions/793 ... complexity