J'ai n tâches, chacune ayant une date limite et un temps d'exécution spécifiques. Cependant, je ne peux pas terminer toutes les tâches dans les délais impartis. Je dois organiser ces tâches de manière à minimiser le délai de la tâche par rapport au temps de réalisation. Considérons ce cas (les valeurs de gauche sont les délais et les valeurs de droite sont le temps que prend la tâche) :
2 2
1 1
4 3
Ces trois tâches peuvent être effectuées de manière optimale comme suit :
temps 1 : tâche 2 - tâche 1 terminée ; 0 dépassement pour la tâche 2
temps 2 : tâche 1
temps 3 : tâche 1 - tâche 2 terminées ; 1 dépassement pour la tâche 1
temps 4 : tâche 3
temps 5 : tâche 3
temps 6 : tâche 3 - tâche 3 terminée ; 3 dépassements pour la tâche 3
J'ai besoin d'un algorithme plus rapide pour cela ; mon objectif est de trouver le dépassement maximum de tous les dépassements (dans le cas ci-dessus, c'est 3). Pour l'instant, je trie les tâches en fonction des délais, mais ce n'est pas rapide, car lorsqu'une nouvelle tâche est ajoutée, je dois trier la liste entière. Existe-t-il un autre moyen ?
Après la suggestion de Lawrey, j'utilise PriorityQueue mais cela ne me donne pas un tri exact. Voici mon code :
class Compare2DArray implements Comparator<int[]> {
public int compare(int a[], int b[]) {
for (int i = 0; i < a.length && i < b.length; i++)
if (a[i] != b[i])
return a[i] - b[i];
return a.length - b.length;
}
}
public class MyClass{
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
int numberOfInputs= scan.nextInt();
PriorityQueue<int[]> inputsList = new PriorityQueue<int[]>(numberOfInputs,new Compare2DArray());
for (int i = 0; i < numberOfInputs; i++) {
int[] input = new int[2];
input[0] = scan.nextInt();
input[1] = scan.nextInt();
inputsList.add(input);
}
}Mais c'est le tri de cette file de tableaux
2 2
1 1
4 3
10 1
2 1
comme
1 1
2 1
4 3
10 1
2 2
au lieu de
1 1
2 1
2 2
4 3
10 1
Le même comparateur fonctionne bien pour le tri des listes. Je ne comprends pas ce qui ne va pas avec PriorityQueueue.
