I have a list of tasks of size n and the time taken to process is represented as tasks[i], where i is index for the task.
Processing Step: These tasks should be processed sequentially from i = 0 to i = n-1, one after the other.
Now there is another list of programmers of size m, who can work on the tasks for a specified duration represented by programmers[i], where i is the index.
A task is said to be completed if its value is 0, otherwise it is a pending task.
So if there are some tasks pending by end of above mentioned processing step, processing should start again from i = 0 to i = n-1
If all tasks are finished, then we can load the tasks back and start the processing from beginning.
I want to collect how many tasks are still pending after each programmer works for their specified duration.
Here is an example:
n=5, tasks = [2, 4, 5, 1, 1]
m=5, programmers = [1, 5, 1, 5, 2]
| Programmer | Tasks | Pending tasks |
|---|---|---|
| 1 | [1, 4, 5, 1, 1] |
The first task is partially processed, total pending tasks = 5 |
| 2 | [0, 0, 5, 1, 1] |
The first two tasks are fully processed, total pending tasks = 3 |
| 3 | [0, 0, 4, 1, 1] |
The third task is partially processed, total pending tasks = 3 |
| 4 | [0, 0, 0, 0, 1] |
The third and fourth tasks are fully processed, total pending tasks = 1 |
| 5 | [0, 0, 0, 0, 0] |
The last task is fully processed, total pending tasks = 0 |
Hence, the number of pending tasks = [5, 3, 3, 1, 0]
tasks = [1, 2, 4, 1, 2]
programmers = [3, 10, 1, 1, 1]
| Programmer | Tasks | Pending tasks |
|---|---|---|
| 1 | [0, 0, 4, 1, 2] |
The first and second tasks are fully processed, total pending tasks = 3 |
| 2 | [0, 0, 0, 0, 0] |
All tasks are fully processed, total pending tasks = 0 (Pending is 0 so load back all tasks [1,2,4,1,2]) |
| 3 | [0, 2, 4, 1, 2] |
The first task is fully processed, total pending tasks = 4 |
| 4 | [0, 1, 4, 1, 2] |
The second task is partially processed, total pending tasks = 4 |
| 5 | [0, 0, 3, 1, 2] |
The second task is fully processed, total pending tasks = 3 |
Output = [3,0,4,4,3]
tasks = [1, 4, 4]
programmers = [9, 1, 4]
Output = [0, 2, 1]
Here is my code that runs in O(m*n) time:
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]
}
}
I also tried using PriorityQueue to process only pending tasks:
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]
}
}
But above code also runs in O(n*m*log(m)) time complexity
Constraints:
n and m in range 1 to 2 * 10^5
each item in input lists is 1 to 10^9
I want to know how to solve this in less time complexity
We can compute the prefix sum array for the task durations, then binary search on each iteration for the first point where the total task duration is more than the amount of work the current programmer can do (for a time complexity of O(m log n)).
public static List<Integer> getPendingTasks(List<Integer> tasks, List<Integer> programmers) {
var res = new ArrayList<Integer>(programmers.size());
var sum = new long[tasks.size() + 1];
for (int i = 1; i <= tasks.size(); i++) sum[i] = sum[i - 1] + tasks.get(i - 1);
int prev = 0;
long extra = 0;
for (int work : programmers) {
if (work >= sum[tasks.size()] - sum[prev] + extra) {
res.add(0);
extra = prev = 0;
continue;
}
int low = prev, high = tasks.size();
while (low <= high) {
int mid = low + high >>> 1;
if (sum[mid] - sum[prev] + extra > work) high = mid - 1;
else low = mid + 1;
}
extra = sum[low] - sum[prev] + extra - work;
prev = low;
res.add(tasks.size() - low + (extra > 0 ? 1 : 0));
}
return res;
}