求解完成任务的最短时间：一种基于扫描线的算法教程

import java.util.*;

class Solution {
    public int minTimeToFinishTasks(List<List<Integer>> tasks) {
        List<int[]> events = new ArrayList<>();
        for (List<Integer> 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<int[]> 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<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 result = solution.minTimeToFinishTasks(tasks);
        System.out.println("Minimum time to finish tasks: " + result); // Output: 4
    }
}