Vorgegebene Aufgaben und Programmierer lösen die Aufgaben in kürzerer Zeit ⇐ Java

[Guest]

Ich habe eine Liste von Aufgaben der Größe n und die zur Verarbeitung benötigte Zeit wird als Aufgaben dargestellt, wobei i der Index für die Aufgabe ist.
Verarbeitungsschritt: Diese Aufgaben sollten sequentiell von i = 0 bis i = n-1, eine nach der anderen, abgearbeitet werden.
Jetzt gibt es eine weitere Liste von Programmierern der Größe m, Wer kann an den Aufgaben für eine bestimmte Dauer arbeiten, dargestellt durch Programmers, wobei i der Index ist.
Eine Aufgabe gilt als abgeschlossen, wenn Sein Wert ist 0, andernfalls handelt es sich um eine ausstehende Aufgabe.
Wenn also am Ende des oben genannten Verarbeitungsschritts einige Aufgaben ausstehen, sollte die Verarbeitung erneut bei i = 0 beginnen zu i = n-1
Wenn alle Aufgaben sind abgeschlossen, dann können wir die Aufgaben zurückladen und die Verarbeitung von vorne beginnen.
Ich möchte erfassen, wie viele Aufgaben noch ausstehen, nachdem jeder Programmierer für die angegebene Dauer gearbeitet hat.
Hier ist ein Beispiel:
Beispiel 1
n=5, Aufgaben = [2, 4, 5, 1 , 1]
m=5, Programmierer = [1, 5, 1, 5, 2]

< thead>

Programmierer
Aufgaben
Ausstehende Aufgaben




1

Code: Select all

[1, 4, 5, 1, 1]

Die erste Aufgabe ist teilweise verarbeitet, insgesamt ausstehende Aufgaben = 5


2

Code: Select all

[0, 0, 5, 1, 1]

Die ersten beiden Aufgaben sind vollständig verarbeitet, insgesamt ausstehende Aufgaben = 3


3

Code: Select all

[0, 0, 4, 1, 1]

Die dritte Aufgabe ist teilweise verarbeitet, insgesamt ausstehende Aufgaben = 3


4

Code: Select all

[0, 0, 0, 0, 1]

Die dritte und vierte Aufgabe sind vollständig verarbeitet, insgesamt ausstehende Aufgaben = 1


5

Code: Select all

[0, 0, 0, 0, 0]

Die letzte Aufgabe ist vollständig verarbeitet, Gesamtzahl der ausstehenden Aufgaben = 0



Daher ist die Anzahl der ausstehenden Aufgaben = [5, 3, 3, 1, 0]
Beispiel 2
tasks = [1, 2, 4, 1, 2]
programmierer = [3, 10, 1, 1, 1]



Programmierer
Aufgaben
Ausstehende Aufgaben




1

Code: Select all

[0, 0, 4, 1, 2]

Die erste und zweite Aufgabe sind vollständig verarbeitet, insgesamt ausstehende Aufgaben = 3


2

Code: Select all

[0, 0, 0, 0, 0]

Alle Aufgaben sind vollständig verarbeitet, Gesamtzahl der ausstehenden Aufgaben = 0 (Ausstehend ist 0, also alle Aufgaben zurückladen [1,2,4,1,2] )


3

Code: Select all

[0, 2, 4, 1, 2]

Die erste Aufgabe ist vollständig verarbeitet, insgesamt ausstehende Aufgaben = 4


4

Code: Select all

[0, 1, 4, 1, 2]

Die zweite Aufgabe ist teilweise verarbeitet, insgesamt ausstehende Aufgaben = 4


5

Code: Select all

[0, 0, 3, 1, 2]

Die zweite Aufgabe ist vollständig verarbeitet, insgesamt ausstehende Aufgaben = 3



Ausgabe = [3,0,4,4,3]
Beispiel 3
Aufgaben = [1, 4, 4]
Programmierer = [9, 1, 4]
Ausgabe = [0, 2, 1]
Hier ist mein Code, der in O(m*n) Zeit ausgeführt wird:

Code: Select all

import java.util.*;

public class Main {

public static List getPendingTasks(List tasks, List programmers) {
List pendingTasks = new ArrayList();
List originalTasks = new ArrayList(tasks); // Save original tasks for reloading
int n = tasks.size();

for (int programmer : programmers) {
int timeRemaining = programmer;
for (int i = 0; i < n && timeRemaining > 0; i++) {
if (tasks.get(i) >  0) {
if (tasks.get(i)  0) {
pending++;
}
}

pendingTasks.add(pending);

// Reload tasks if all are completed
if (pending == 0) {
tasks = new ArrayList(originalTasks);
}
}

return pendingTasks;
}

public static void main(String[] args) {
// Example 1
List tasks1 = Arrays.asList(2, 4, 5, 1, 1);
List programmers1 = Arrays.asList(1, 5, 1, 5, 2);
System.out.println("Output: " + getPendingTasks(tasks1, programmers1)); // Output: [5, 3, 3, 1, 0]

// Example 2
List tasks2 = Arrays.asList(1, 2, 4, 1, 2);
List programmers2 = Arrays.asList(3, 10, 1, 1, 1);
System.out.println("Output: " + getPendingTasks(tasks2, programmers2)); // Output: [3, 0, 4, 4, 3]

// Example 3
List tasks3 = Arrays.asList(1, 4, 4);
List programmers3 = Arrays.asList(9, 1, 4);
System.out.println("Output: " + getPendingTasks(tasks3, programmers3)); // Output: [0, 2, 1]
}
}

Ich habe auch versucht, PriorityQueue zu verwenden, um nur ausstehende Aufgaben zu verarbeiten:

Code: Select all

import java.util.*;

class Main {

public static List getPendingTasks(List tasks, List programmer) {
List result = new ArrayList();
Queue pending = new PriorityQueue();
int n = tasks.size();
List originalTasks = new ArrayList(tasks);

// Initialize set with all tasks
for (int i = 0; i < n; i++) {
pending.add(i);
}
Queue q = new PriorityQueue(pending);

// Process each item
for (int p : programmer) {
int timeAvailable = p;

// Process only unprocessed tasks
List balancedTask = new ArrayList();

while (!q.isEmpty()) {
int i = q.poll();
if (tasks.get(i)