Tarefas dadas e programadores resolvem as tarefas em menos tempo

Tenho uma lista de tarefas de tamanho ne o tempo gasto para processar é representado como tasks[i], onde ié o índice da tarefa.

Etapa de processamento: Essas tarefas devem ser processadas sequencialmente de i = 0a i = n-1, uma após a outra.

Agora há outra lista de programadores de tamanho m, que podem trabalhar nas tarefas por uma duração especificada representada por programmers[i], onde ié o índice.

Diz-se que uma tarefa está concluída se seu valor for 0; caso contrário, é uma tarefa pendente.

Portanto, se houver algumas tarefas pendentes até o final da etapa de processamento mencionada acima, o processamento deverá ser reiniciado de i = 0parai = n-1

Se todas as tarefas forem concluídas, podemos carregá-las novamente e iniciar o processamento do início.

Quero coletar quantas tarefas ainda estão pendentes depois que cada programador trabalha durante o período especificado.

Aqui está um exemplo:

Exemplo 1

n=5, tarefas = [2, 4, 5, 1, 1] m=5, programadores =[1, 5, 1, 5, 2]

Portanto, o número de tarefas pendentes =[5, 3, 3, 1, 0]

Exemplo 2

tarefas = [1, 2, 4, 1, 2] programadores =[3, 10, 1, 1, 1]

Saída =[3,0,4,4,3]

Exemplo 3

tarefas = [1, 4, 4] programadores =[9, 1, 4]

Saída =[0, 2, 1]

Aqui está meu código que roda em tempo O(m*n):

import java.util.*;

public class Main {

    public static List<Integer> getPendingTasks(List<Integer> tasks, List<Integer> programmers) {
        List<Integer> pendingTasks = new ArrayList<>();
        List<Integer> 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) <= timeRemaining) {
                        timeRemaining -= tasks.get(i);
                        tasks.set(i, 0);
                    } else {
                        tasks.set(i, tasks.get(i) - timeRemaining);
                        timeRemaining = 0;
                    }
                }
            }

            // Count pending tasks
            int pending = 0;
            for (int task : tasks) {
                if (task > 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<Integer> tasks1 = Arrays.asList(2, 4, 5, 1, 1);
        List<Integer> programmers1 = Arrays.asList(1, 5, 1, 5, 2);
        System.out.println("Output: " + getPendingTasks(tasks1, programmers1)); // Output: [5, 3, 3, 1, 0]

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

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

Também tentei usar PriorityQueue para processar apenas tarefas pendentes:

import java.util.*;

class Main {

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

        // Initialize set with all tasks
        for (int i = 0; i < n; i++) {
            pending.add(i);
        }
        Queue<Integer> q = new PriorityQueue<>(pending);
        
        // Process each item
        for (int p : programmer) {
            int timeAvailable = p;

            // Process only unprocessed tasks
            List<Integer> balancedTask = new ArrayList<>();
            
            while (!q.isEmpty()) {
                int i = q.poll();
                if (tasks.get(i) <= timeAvailable) {
                    timeAvailable -= tasks.get(i);
                    // Task fully processed
                } else {
                    tasks.set(i, tasks.get(i) - timeAvailable); // Partially processed
                    timeAvailable = 0; // time exhausted
                    balancedTask.add(i);
                }
            }
            q.addAll(balancedTask);
            result.add(q.size());
            if(q.size() ==0) {
                tasks = originalTasks;
                q= pending;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(getPendingTasks(Arrays.asList(2, 4, 5, 1, 1), Arrays.asList(1, 5, 1, 5, 2))); 
        // Expected: [5, 3, 3, 1, 0]
        
        System.out.println(getPendingTasks(Arrays.asList(1, 2, 4, 1, 2), Arrays.asList(3, 10, 1, 1, 1))); 
        // Expected: [3, 0, 4, 4, 3]
        
        System.out.println(getPendingTasks(Arrays.asList(1, 4, 4), Arrays.asList(9, 1, 4))); 
        // Expected: [0, 2, 1]
    }
}

Mas o código acima também é executado em O(n*m*log(m))complexidade de tempo

Restrições:

n and m in range 1 to 2 * 10^5
each item in input lists is 1 to 10^9

Quero saber como resolver isso em menos complexidade de tempo