最小化完成任务所需时间：一种基于扫描线的解决方案-java教程-PHP中文网

最小化完成任务所需时间：一种基于扫描线的解决方案

聖光之護

发布： 2025-08-22 18:44:17

原创

477人浏览过

最小化完成任务所需时间：一种基于扫描线的解决方案

本文旨在解决一个时间优化问题：给定一组任务，每个任务需要在特定时间范围内完成一定的时长，目标是找到完成所有任务所需的最小总时间。任务可以并行处理，且所需时间段可以是不连续的。本文将详细介绍一种基于扫描线算法的解决方案，并提供 Java 代码示例。

问题描述

假设我们有一系列任务，每个任务由 [begin, end, period] 三元组表示，其中：

begin：任务的起始时间（包含）。
end：任务的结束时间（包含）。
period：完成任务所需的总时长。

我们需要找到一个最小的时间集合，使得每个任务都能在其指定的时间范围内完成所需的时长。

扫描线算法

扫描线算法是一种常用的解决几何问题的算法，其核心思想是将问题转化为一系列在扫描线上进行的事件处理。在本问题中，我们将时间轴作为扫描线，将每个任务的起始和结束时间点作为事件。

腾讯小微

基于微信AI智能对话系统打造的智能语音助手解决方案

查看详情

算法步骤：

构建事件列表： 对于每个任务 [begin, end, period]，创建两个事件：
- 起始事件：(begin, period, "start")，表示任务开始。
- 结束事件：(end, begin, "end")，表示任务结束（这里存储begin只是为了方便后续查找对应的起始事件）。
排序事件列表： 将所有事件按照时间顺序排序。
扫描时间线： 遍历排序后的事件列表，维护一个活动任务栈。
- 起始事件： 当遇到起始事件 (time, period, "start") 时，将其加入活动任务栈 stack。stack中存储(beginTime, timeLeft)，表示任务的起始时间和剩余需要完成的时间。
- 结束事件： 当遇到结束事件 (time, begin, "end") 时，找到与该结束事件对应的起始事件，计算剩余时间，并从活动任务栈中移除该任务，并更新总时间。
  - 计算起始事件对应任务的剩余时间timeLeft。
  - 将timeLeft累加到结果res中，因为这些时间是必须花费的。
  - 遍历活动任务栈，对栈中的每个任务，可以最多扣除timeLeft时间，如果栈中任务的剩余时间大于timeLeft，则扣除timeLeft，否则扣除栈中任务的剩余时间。

Java 代码示例

import java.util.*;

public class MinTaskTime {

    public static int minTimeToFinishTasks(List<List<Integer>> tasks) {
        List<int[]> events = new ArrayList<>();
        for (List<Integer> task : tasks) {
            int begin = task.get(0);
            int end = task.get(1);
            int period = task.get(2);
            events.add(new int[]{begin, period, 0}); // 0 for start
            events.add(new int[]{end, begin, 1});   // 1 for end, store begin for finding the task
        }

        // Sort events by time
        Collections.sort(events, (a, b) -> a[0] - b[0]);

        int res = 0;
        Stack<int[]> stack = new Stack<>(); // Store [startTime, timeLeft]

        for (int[] event : events) {
            int time = event[0];
            int periodOrBegin = event[1];
            int type = event[2];

            if (type == 0) { // Start event
                stack.push(new int[]{time, periodOrBegin});
            } else { // End event
                int beginTime = periodOrBegin; // Retrieve begin time from the end event
                int timeLeft = 0;
                // Find the corresponding task and calculate timeLeft
                for(int i = 0; i < stack.size(); i++){
                    if(stack.get(i)[0] == beginTime){
                        timeLeft = stack.get(i)[1];
                        stack.remove(i);
                        break;
                    }
                }

                res += timeLeft;

                // Subtract time from active tasks in the stack
                int subtract = timeLeft;
                List<int[]> tempStack = new ArrayList<>(); // Use a temporary stack to avoid ConcurrentModificationException
                while (!stack.isEmpty() && subtract > 0) {
                    int[] activeTask = stack.pop();
                    int startTime = activeTask[0];
                    int remainingTime = activeTask[1];

                    if (remainingTime <= subtract) {
                        subtract -= remainingTime;
                    } else {
                        activeTask[1] -= subtract;
                        subtract = 0;
                        tempStack.add(activeTask); // Push back the task with remaining time
                    }
                }
                // Push the remaining tasks back to the stack
                for(int i = tempStack.size() - 1; i >= 0; i--){
                    stack.push(tempStack.get(i));
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        List<List<Integer>> 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
    }
}

登录后复制