我有一个大小为 n 的任务列表，处理所需的时间表示为tasks[i]，其中 i 是任务的索引。
处理步骤： 这些任务应从 i=0 到 i=n-1 依次处理。
现在有另一个大小为 m 的程序员列表，他们可以在由程序员[i]表示的指定持续时间内完成任务，其中 i 是索引。
工作是循环程序员并按顺序处理任务，如果所有任务在某个程序员中间完成，那么我们可以重新加载所有任务并为其余程序员进行处理（详细信息请查看示例2）。
如果任务的值为0，则表示任务已完成，否则为待处理任务。
因此，如果在上述处理步骤结束时还有一些任务待处理，则应从 i=0 到 i=n-1 重新开始处理
如果所有任务都完成了，那么我们可以加载任务并从头开始处理
我想收集每个程序员在指定的时间内工作后仍有多少待处理的任务。
这是一个例子：
**Example: 1 **
n=5，任务 = [2, 4, 5, 1, 1] m=5, 程序员 = [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]
示例：2
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]
**Example: 3**
tasks = [1, 4, 4]
programmers = [9, 1, 4]
Output = [0, 2, 1]
这是我在 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]
}
}
我还尝试使用 PriorityQueue 仅处理待处理的任务：
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]
}
}
但是上面的代码也以
O(n*m*log(m))限制：
n and m in range 1 to 2 * 10^5
each item in input lists is 1 to 10^9
我想知道如何以较短的时间复杂度解决这个问题
我们可以计算任务持续时间的前缀和数组，然后在每次迭代中二分搜索第一个点，其中总任务持续时间大于当前程序员可以完成的工作量（时间复杂度为
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;
}