本文详细介绍了如何使用扫描线算法解决“求解完成任务的最短时间”问题。该问题涉及在给定的时间范围内完成多个任务，每个任务都有起始时间、结束时间和所需完成时间。本文将深入探讨算法逻辑，并通过Java代码示例展示如何有效地计算完成所有任务所需的最小时间。
问题描述
给定一个任务数组 tasks，其中每个任务表示为 [begin, end, period]，分别表示任务的起始时间、结束时间和所需完成时间。任务必须在 begin 和 end 之间完成，且 period 表示完成任务所需的总时间。允许并行处理多个任务，目标是找到完成所有任务所需的最小时间。
算法思路：扫描线算法
解决此问题的有效方法是使用扫描线算法。该算法的核心思想是将任务的起始和结束时间点视为事件，然后按时间顺序扫描这些事件。
- 事件拆分和排序： 将每个任务 [begin, end, period] 拆分为两个事件：起始事件 (begin, period, "start") 和结束事件 (end, begin, "end")。然后，将所有事件按时间顺序排序。注意结束事件需要携带开始时间信息，方便后续处理。
- 扫描过程： 维护一个栈（或者优先队列）来存储当前活跃的任务。当遇到起始事件时，将其添加到栈中。当遇到结束事件时，找到对应的起始事件，并计算该任务剩余需要完成的时间。然后，从栈中移除该任务，并更新栈中其他任务的剩余时间。
- 时间累加： 在扫描过程中，累加每个时间点实际执行任务的时间，最终得到完成所有任务所需的最小时间。
Java 代码示例
import java.util.*;
class Solution {
public int minTimeToFinishTasks(List> tasks) {
List events = new ArrayList<>();
for (List task : tasks) {
int start = task.get(0);
int end = task.get(1);
int period = task.get(2);
events.add(new int[]{start, period, 0, end}); // 0 for start
events.add(new int[]{end, period, 1, start}); // 1 for end
}
// Sort events by time, if time is same, process end events first
Collections.sort(events, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
} else {
return a[2] - b[2]; // End events first if time is same
}
});
int res = 0;
List activeTasks = new ArrayList<>(); // Use a list as stack
for (int[] event : events) {
int time = event[0];
int period = event[1];
int type = event[2];
int startTime = event[3];
if (type == 0) { // Start event
activeTasks.add(new int[]{startTime, period});
} else { // End event
// Find the corresponding start event
int timeLeft = 0;
for (int i = 0; i < activeTasks.size(); i++) {
if (activeTasks.get(i)[0] == startTime) {
timeLeft = activeTasks.get(i)[1];
activeTasks.remove(i);
break;
}
}
res += timeLeft;
// Subtract time from other active tasks
int subtract = timeLeft;
for (int i = 0; i < activeTasks.size(); i++) {
int currentPeriod = activeTasks.get(i)[1];
int deduction = Math.min(subtract, currentPeriod);
activeTasks.get(i)[1] -= deduction;
subtract -= deduction;
}
// Remove tasks with period <= 0 from stack after subtraction
activeTasks.removeIf(task -> task[1] <= 0);
}
}
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
List> tasks = new ArrayList<>();
tasks.add(Arrays.asList(1, 3, 2));
tasks.add(Arrays.asList(2, 5, 3));
tasks.add(Arrays.asList(5, 6, 2));
int result = solution.minTimeToFinishTasks(tasks);
System.out.println("Minimum time to finish tasks: " + result); // Output: 4
}
} 代码解释
-
minTimeToFinishTasks(List
- > tasks):
- 事件列表创建： 遍历任务列表，将每个任务拆分为起始事件和结束事件，并添加到事件列表中。起始事件类型标记为0，结束事件类型标记为1。
- 事件排序： 使用 Collections.sort 方法对事件列表进行排序。排序规则是首先按时间升序排列，如果时间相同，则结束事件排在起始事件之前。
-
扫描过程： 遍历排序后的事件列表。
- 起始事件： 将起始事件添加到 activeTasks 列表中。
- 结束事件： 从 activeTasks 列表中找到对应的起始事件，计算该任务剩余需要完成的时间 timeLeft，并将其从 activeTasks 列表中移除。将 timeLeft 加到结果 res 中。然后，遍历 activeTasks 列表，从其他活跃任务中扣除最多 timeLeft 的时间。
- 返回结果： 返回 res，即完成所有任务所需的最小时间。
注意事项
- 事件排序： 正确的事件排序是算法的关键。确保结束事件在相同时间点的起始事件之前处理，以避免时间计算错误。
- 栈的维护： 在处理结束事件后，需要及时清理 activeTasks 列表，移除已经完成的任务，避免对后续计算产生影响。
- 数据结构选择： 优先队列也可以作为activeTasks的数据结构，这样可以更加高效的找到剩余时间最短的任务。
总结
扫描线算法是一种解决此类时间调度问题的有效方法。通过将任务拆分为事件并按时间顺序处理，可以有效地计算完成所有任务所需的最小时间。该算法的时间复杂度主要取决于事件排序的时间复杂度，通常为 O(n log n)，其中 n 是任务的数量。该方法思路清晰，代码实现相对简洁，易于理解和维护。
