最小化完成任务所需的时间：一种扫描线算法教程

import java.util.*;

public class TaskScheduler {

    public static int minTimeToFinishTasks(List<List<Integer>> tasks) {
        List<Event> 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 Event(start, period, true, task)); // Start Event
            events.add(new Event(end, 0, false, task));   // End Event
        }

        // Sort events by time, prioritizing end events in case of ties
        Collections.sort(events, (a, b) -> {
            if (a.time != b.time) {
                return a.time - b.time;
            } else {
                return a.isStart ? 1 : -1; // End events before start events
            }
        });

        int result = 0;
        Stack<TaskInfo> activeTasks = new Stack<>();

        for (Event event : events) {
            if (event.isStart) {
                // Push new task information to the stack
                activeTasks.push(new TaskInfo(event.task.get(0), event.task.get(2)));
            } else {
                // Process end event

                // Find corresponding start event (we don't store the start event directly, but the info)
                int remainingTime = findAndProcessTask(activeTasks, event.task.get(0));

                result += remainingTime;

                // Subtract from other active tasks
                subtractTimeFromActiveTasks(activeTasks, remainingTime);
            }
        }

        return result;
    }

    private static int findAndProcessTask(Stack<TaskInfo> activeTasks, int startTime) {
        TaskInfo taskToRemove = null;
        for (TaskInfo task : activeTasks) {
            if (task.startTime == startTime) {
                taskToRemove = task;
                break;
            }
        }

        if (taskToRemove == null) {
            return 0; // Should not happen if input is valid
        }

        activeTasks.remove(taskToRemove);
        return taskToRemove.remainingTime;
    }

    private static void subtractTimeFromActiveTasks(Stack<TaskInfo> activeTasks, int timeToSubtract) {
        ListIterator<TaskInfo> iterator = activeTasks.listIterator();
        while (iterator.hasNext()) {
            TaskInfo task = iterator.next();
            int subtractedTime = Math.min(task.remainingTime, timeToSubtract);
            task.remainingTime -= subtractedTime;
            timeToSubtract -= subtractedTime;

            if (task.remainingTime == 0) {
                iterator.remove(); // Remove completed task
            }

            if (timeToSubtract == 0) {
                break;
            }
        }
    }


    static class Event {
        int time;
        int period;
        boolean isStart;
        List<Integer> task;

        public Event(int time, int period, boolean isStart, List<Integer> task) {
            this.time = time;
            this.period = period;
            this.isStart = isStart;
            this.task = task;
        }
    }

    static class TaskInfo {
        int startTime;
        int remainingTime;

        public TaskInfo(int startTime, int remainingTime) {
            this.startTime = startTime;
            this.remainingTime = remainingTime;
        }
    }


    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
    }
}