Где недостаток в этом жадном подходе? ⇐ C#

[Anonymous]

Я сижу на проблеме LeetCode, в частности, минимальное время для ремонта автомобилей.
Вы получаете список, сколько у вас механиков и сколько автомобилей вам нужно исправить.
У каждого механика есть звание, и он принимает ранги * (NR фиксированных автомобилей)^2 < /code> для работы. Например. Механик ранга 5 должен починить 10 автомобилей, затем он возьмет 5 * 10^2 , так что 500 время для этого. Чем ниже звание, тем быстрее они работают.
задача состоит в том, чтобы разделить автомобили между механикой, чтобы достичь наименьшего количества времени. Для каждого автомобиля принять наиболее эффективную механику и рассказать ему о повышенном времени, если он должен был починить другой автомобиль.

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

public class Solution {
public long RepairCars(int[] ranks, int cars) {
PriorityQueue q = new(ranks.Length);
int[] repairs = new int[ranks.Length];
for(int i = 0; i < ranks.Length; i++){
q.Enqueue(i, ranks[i]);
}
long max = 0;
for(int i = 0; i < cars; i++){
int mechanic = q.Dequeue();
repairs[mechanic]++;
long time = ranks[mechanic] * repairs[mechanic] * repairs[mechanic];
max = Math.Max(time, max);
q.Enqueue(mechanic, ranks[mechanic] * (repairs[mechanic]+1) * (repairs[mechanic]+1));
}
return max;
}
}

После консультации с решениями я вижу, что мне следует использовать с подходом к бинарному поиску только по причинам производительности. LeetCode ожидает, что это потребует 23583883332 , в то время как мой код дает мне максимальное время 2147181372 , так что просто на 10% лучше распределения.
Механики имеют следующие ранги: [31,31,5,19,19,10,31,18,19,3,16,20,4,16,2,25,10,16,23,18,21,23,28,6,7,29,11,11,19, 20,24,19,26,12,29,29,1,14,17,26,24,7,11,28,22,14,31,12,3,19,16,26,11]
Я вижу, что мой алгоритм медленный, но я не вижу, чтобы это не так. Но мне также трудно поверить, что я первый и только один на LeetCode, чтобы заметить неправильный тестовый приход. Жадный подход может быть медленнее, но почему это было неправильно?

Подробнее здесь: https://stackoverflow.com/questions/797 ... y-approach