无重叠合并多场景公共任务的Java实现算法咨询

需求说明 #

现有多组有固定执行顺序的任务链路，需合并公共任务实现仅执行一次，合并规则要求新增公共任务不能与已合并的作业范围产生重叠，避免逻辑冲突。

可选算法方案 #

采用公共任务匹配+区间重叠校验的组合方案即可覆盖需求，复杂多依赖场景可扩展使用DAG拓扑排序优化：

1. 预处理阶段 #

为每个任务生成唯一标识，规则为任务类型ID + 入参哈希值，仅逻辑完全一致的任务会被判定为可合并的公共任务，避免同名不同逻辑的任务被错误合并。

2. 公共任务筛选 #

遍历所有输入链路，提取在所有链路中都存在、且相对执行顺序完全一致的任务，作为待合并的候选公共任务集合。

3. 重叠校验与合并 #

• 初始化集合记录所有已合并任务在各链路中的位置区间
• 遍历候选公共任务，校验该任务在各链路中的位置是否与已合并区间重叠，若重叠直接跳过，若不重叠则标记为全局公共任务，将对应位置加入已合并区间集合

4. 生成最终执行链路 #

保留原始链路的执行顺序，将重复的公共任务替换为全局执行结果引用，非公共任务保留原执行逻辑，得到最终无重复执行的合并链路。

Java实现示例 #

import lombok.Data;
import java.util.*;
import java.util.stream.Collectors;

// 任务实体定义
@Data
class Task {
    // 唯一标识：任务ID+入参哈希，确保相同逻辑的任务标识一致
    private String uniqueId;
    private String taskName;
    // 任务在所属链路中的位置索引
    private int position;
}

// 任务合并工具类
public class TaskMergeHelper {
    /**
     * 合并多组任务链路，去重公共不重叠任务
     * @param taskChains 输入的多组任务链路
     * @return 合并后的最终执行链路
     */
    public List<Task> mergeTaskChains(List<List<Task>> taskChains) {
        if (taskChains == null || taskChains.isEmpty()) {
            return Collections.emptyList();
        }
        // 提取所有链路的公共任务ID集合
        Set<String> commonTaskIds = getCommonTaskUniqueIds(taskChains);
        // 记录已合并的任务位置集合，用于重叠校验
        Set<Integer> mergedPositions = new HashSet<>();
        List<Task> mergedResult = new ArrayList<>();
        // 以第一条链路为基准遍历生成合并结果
        for (Task baseTask : taskChains.get(0)) {
            String taskId = baseTask.getUniqueId();
            // 非公共任务直接加入结果
            if (!commonTaskIds.contains(taskId)) {
                mergedResult.add(baseTask);
                continue;
            }
            // 校验当前任务是否和已合并区间重叠
            boolean isOverlap = checkTaskOverlap(taskId, taskChains, mergedPositions);
            if (!isOverlap) {
                mergedResult.add(baseTask);
                // 将该任务在所有链路中的位置标记为已合并
                markTaskPositionAsMerged(taskId, taskChains, mergedPositions);
            }
        }
        return mergedResult;
    }

    private Set<String> getCommonTaskUniqueIds(List<List<Task>> taskChains) {
        Set<String> commonIds = taskChains.get(0).stream()
                .map(Task::getUniqueId)
                .collect(Collectors.toSet());
        for (int i = 1; i < taskChains.size(); i++) {
            Set<String> currentChainIds = taskChains.get(i).stream()
                    .map(Task::getUniqueId)
                    .collect(Collectors.toSet());
            commonIds.retainAll(currentChainIds);
        }
        return commonIds;
    }

    private boolean checkTaskOverlap(String taskUniqueId, List<List<Task>> taskChains, Set<Integer> mergedPositions) {
        for (List<Task> chain : taskChains) {
            Optional<Task> targetTask = chain.stream()
                    .filter(t -> taskUniqueId.equals(t.getUniqueId()))
                    .findFirst();
            if (targetTask.isPresent() && mergedPositions.contains(targetTask.get().getPosition())) {
                return true;
            }
        }
        return false;
    }

    private void markTaskPositionAsMerged(String taskUniqueId, List<List<Task>> taskChains, Set<Integer> mergedPositions) {
        for (List<Task> chain : taskChains) {
            chain.stream()
                    .filter(t -> taskUniqueId.equals(t.getUniqueId()))
                    .forEach(t -> mergedPositions.add(t.getPosition()));
        }
    }
}

注：上述代码使用lombok简化实体类代码，若项目未引入lombok，手动为Task类添加getter、setter、equals、hashCode方法即可正常运行。

扩展优化 #

如果任务链路存在复杂的前后依赖关系，可将任务链路转换为有向无环图（DAG），基于拓扑排序做公共节点的去重合并，能更好地保证执行顺序的正确性。

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