求解给定任务的最短处理时间：寻求Java/Python正确实现方案

给定任务数组，每个任务格式为[begin, end, period]，要求每个任务在[begin, end]（包含两端）的时间范围内完成，period为完成任务所需的不连续时长，且可同时处理无限任务。目标是找出完成所有任务的最短处理时间点总数。

示例输入：

[[1,3,2],[2,5,3],[5,6,2]]

示例输出：4
解释：选择时间点2、3、5、6即可完成所有任务，其中任务0用2、3，任务1用2、3、5，任务2用5、6。

你的实现问题分析 #

你的代码存在两个核心问题：

1. 变量名冲突：方法内定义了Set<Integer> s，后续又定义int s = p.get(0)，会直接导致编译错误。
2. 贪心策略错误：你优先使用已有的时间点，但没有优先选择任务窗口的末尾时间点，这会导致后续任务无法最大化复用已选时间点，最终总时间点数量不是最优。比如若任务0选了1、2，任务1还需选3、4、5，任务2选5、6，总时间点会达到6个，远大于最优解。

正确贪心思路 #

要最小化总工作时间点，核心是让尽可能多的任务共享同一个时间点。最优策略如下：

1. 将所有任务按end（结束时间）从小到大排序。
2. 维护一个已选时间点的集合（用有序结构可提升查询效率）。
3. 对每个任务：
   • 统计该任务时间窗口[begin, end]内已有的已选时间点数量。
   • 若已有的数量不足period，则从end开始倒着往begin遍历，将未被选中的时间点加入集合，直到满足period要求。

该策略的合理性：按结束时间排序后，后续任务的结束时间不会早于当前任务，优先选当前任务的末尾时间点，能最大化这个时间点被后续任务复用的概率，从而减少总时间点数量。

Java 实现 #

import java.util.*;

public class TaskScheduler {
    public static int process(List<List<Integer>> tasks) {
        // 按任务结束时间升序排序
        tasks.sort(Comparator.comparingInt(task -> task.get(1)));
        
        // TreeSet存储已选时间点，支持范围查询和有序遍历
        TreeSet<Integer> selected = new TreeSet<>();
        
        for (List<Integer> task : tasks) {
            int begin = task.get(0);
            int end = task.get(1);
            int period = task.get(2);
            
            // 统计当前窗口内已选时间点数量
            int count = 0;
            Integer time = selected.ceiling(begin);
            while (time != null && time <= end) {
                count++;
                time = selected.higher(time);
            }
            
            int need = period - count;
            if (need > 0) {
                // 从end倒序补充时间点
                for (int t = end; t >= begin && need > 0; t--) {
                    if (!selected.contains(t)) {
                        selected.add(t);
                        need--;
                    }
                }
            }
        }
        
        return selected.size();
    }

    public static void main(String[] args) {
        List<List<Integer>> tasks = Arrays.asList(
            Arrays.asList(1,3,2),
            Arrays.asList(2,5,3),
            Arrays.asList(5,6,2)
        );
        System.out.println(process(tasks)); // 输出4
    }
}

Python 实现 #

def process(tasks):
    # 按任务结束时间升序排序
    tasks.sort(key=lambda x: x[1])
    selected = set()
    
    for begin, end, period in tasks:
        # 统计当前窗口内已选时间点数量
        count = sum(1 for t in selected if begin <= t <= end)
        
        need = period - count
        if need > 0:
            # 从end倒序补充时间点
            t = end
            while need > 0 and t >= begin:
                if t not in selected:
                    selected.add(t)
                    need -= 1
                t -= 1
    
    return len(selected)

# 测试示例
tasks = [[1,3,2],[2,5,3],[5,6,2]]
print(process(tasks)) # 输出4

内容的提问来源于stack exchange，提问作者Learner