本文档详细介绍了如何使用扫线算法解决最小化完成给定任务集合所需时间的问题。每个任务都有开始时间、结束时间和完成所需的时长。目标是找到完成所有任务所需的最短时间，任务可以并行处理，且任务时间段可以是不连续的。本文将提供清晰的算法逻辑、示例代码和详细的解释，帮助读者理解和应用该方法。
问题描述
给定一个任务列表，其中每个任务由 [begin, end, period] 三个元素组成，分别表示任务的开始时间、结束时间和完成任务所需的时长。我们需要找到完成所有任务所需的最小时间。
约束条件：
- 任务需要在 begin 和 end 时间点之间完成（包含 begin 和 end）。
- 任务的 period 可以是不连续的时间段。
- 可以同时处理任意数量的任务。
算法思路：扫线算法
扫线算法是一种常用的解决时间区间问题的有效方法。其核心思想是将时间轴离散化，通过模拟时间流逝，在关键时间点（事件点）进行状态更新，从而求解问题。
对于本问题，我们可以将每个任务的开始时间和结束时间看作事件点。然后，按照时间顺序处理这些事件点。
- 事件点生成： 将每个任务的开始时间和结束时间拆分成独立的事件点，并标记事件类型（开始或结束）。
- 事件点排序： 将所有事件点按照时间顺序排序。如果时间相同，结束事件优先于开始事件。
-
扫描处理： 遍历排序后的事件点，维护一个活跃任务栈。
- 开始事件： 当遇到一个任务的开始事件时，将任务信息（开始时间，剩余时长）压入栈中。
- 结束事件： 当遇到一个任务的结束事件时，找到栈中对应的开始事件，计算该任务还需要的时长，然后从栈中移除该任务，并将剩余时长从其他活跃任务中扣除。
Java 代码示例
import java.util.*;
public class MinTaskTime {
public static int minTimeToFinishTasks(List> tasks) {
List events = new ArrayList<>();
for (List task : tasks) {
int start = task.get(0);
int end = task.get(1);
int duration = task.get(2);
events.add(new int[]{start, duration, 0}); // 0 for start
events.add(new int[]{end, duration, 1}); // 1 for end
}
// Sort events by time, end events come first if times are equal
Collections.sort(events, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
} else {
return a[2] - b[2]; // End events before start events
}
});
Stack activeTasks = new Stack<>();
int totalTime = 0;
for (int[] event : events) {
int time = event[0];
int duration = event[1];
int type = event[2];
if (type == 0) { // Start event
activeTasks.push(new int[]{time, duration});
} else { // End event
int need = 0;
// find the corresponding start event
for(int i = 0; i < activeTasks.size(); i++){
int[] task = activeTasks.get(i);
if(task[0] == time && task[1] == duration){
need = task[1];
activeTasks.remove(i);
break;
}
}
totalTime += need;
// Subtract time from other active tasks
int subtract = need;
for (int[] task : activeTasks) {
int reduce = Math.min(subtract, task[1]);
task[1] -= reduce;
subtract -= reduce;
}
// Clean up tasks with duration 0
activeTasks.removeIf(task -> task[1] == 0);
}
}
return totalTime;
}
public static void main(String[] args) {
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 minTime = minTimeToFinishTasks(tasks);
System.out.println("Minimum time to finish all tasks: " + minTime); // Output: 4
}
} 代码解释
-
minTimeToFinishTasks(List
- > tasks) 函数：
- 接收一个任务列表作为输入。
- 创建一个 events 列表，用于存储事件点（开始和结束）。
- 遍历任务列表，将每个任务的开始和结束时间添加到 events 列表中，并标记事件类型。
- 使用 Collections.sort() 对 events 列表进行排序。排序规则是先按照时间顺序，如果时间相同，结束事件优先于开始事件。
- 创建一个 activeTasks 栈，用于存储活跃任务。
- 遍历排序后的 events 列表。
- 如果当前事件是开始事件，则将任务信息（开始时间，剩余时长）压入 activeTasks 栈中。
- 如果当前事件是结束事件，则从 activeTasks 栈中找到对应的开始事件，计算该任务还需要的时长 need，然后将该时长加到 totalTime 中。并将剩余时长从其他活跃任务中扣除。
- 返回 totalTime。
示例分析
对于输入 [[1,3,2],[2,5,3],[5,6,2]]：
-
事件点生成：
- (1, 2, start)
- (2, 3, start)
- (3, 2, end)
- (5, 3, start)
- (5, 3, end)
- (6, 2, end)
-
事件点排序：
- (1, 2, start)
- (2, 3, start)
- (3, 2, end)
- (5, 3, start)
- (5, 3, end)
- (6, 2, end)
-
扫描处理：
- 时间 1：遇到 (1, 2, start)，activeTasks = [(1, 2)]
- 时间 2：遇到 (2, 3, start)，activeTasks = [(1, 2), (2, 3)]
- 时间 3：遇到 (3, 2, end)，找到对应的 (1, 2)，need = 2，totalTime = 2。从 activeTasks 中移除 (1, 2)。 activeTasks = [(2, 1)]
- 时间 5：遇到 (5, 2, start)，activeTasks = [(2, 1), (5, 2)]
- 时间 5：遇到 (5, 1, end)，找到对应的 (2, 1)，need = 1，totalTime = 3。从 activeTasks 中移除 (2, 1)。activeTasks = [(5, 1)]
- 时间 6：遇到 (6, 1, end)，找到对应的 (5, 1)，need = 1，totalTime = 4。从 activeTasks 中移除 (5, 1)。activeTasks = []
最终结果为 4。
注意事项
- 在处理结束事件时，需要找到栈中对应的开始事件。可以使用额外的映射关系来加速查找过程。
- 在扣除剩余时长时，需要注意活跃任务的时长可能不足以扣除，需要取最小值。
- 代码示例中的 activeTasks 使用 Stack，也可以使用其他数据结构，如 PriorityQueue，以优化性能。
总结
本文详细介绍了如何使用扫线算法解决最小化完成任务所需时间的问题。该算法通过将时间轴离散化，并模拟时间流逝，在关键时间点进行状态更新，从而求解问题。该方法可以有效地解决时间区间相关的问题，具有较高的实用价值。
