合并Shift对象数组生成最终排班表的技术方案问询

问题背景 #

需要合并两类Shift数组生成最终排班表：

• 原班次数组：连续无间隔，相邻班次的end与下一班次的start完全衔接
• 覆盖班次数组：分散且无重叠，优先级高于原班次，会替换对应时间区间的排班

Shift类型定义：

type Shift = { start: Date, end: Date, users: string[] }

核心挑战是处理覆盖班次的各种场景：完全覆盖原班次、在原班次中间插入、跨多个原班次等。

推荐方案：排序+双指针遍历 #

数据结构选择 #

将覆盖班次按start时间升序排序，结合双指针同步遍历原班次与覆盖班次，既能保证处理逻辑清晰，又能实现高效计算。

算法步骤 #

1. 预处理覆盖班次：复制并按start时间升序排序，确保后续遍历顺序正确
2. 双指针初始化：用两个指针分别指向原班次和覆盖班次的当前处理元素，初始化结果数组为空
3. 同步遍历处理：
   • 若当前覆盖班次的start晚于当前原班次的end：将原班次直接加入结果，原班次指针后移
   • 若当前覆盖班次与原班次时间重叠：
     • 若原班次的start早于覆盖班次的start：将原班次的前半段（未被覆盖部分）加入结果
     • 将覆盖班次加入结果
     • 若覆盖班次的end晚于原班次的end：原班次指针后移，继续检查当前覆盖班次是否与下一个原班次重叠
     • 若覆盖班次的end早于原班次的end：更新原班次的start为覆盖班次的end，继续处理原班次剩余部分
   • 覆盖班次指针后移
4. 收尾处理：遍历结束后，将剩余的原班次或覆盖班次（若有）加入结果

代码实现（TypeScript） #

type Shift = { start: Date, end: Date, users: string[] };

function mergeShifts(originalShifts: Shift[], overrideShifts: Shift[]): Shift[] {
    // 预处理：覆盖班次按start升序排序，避免修改原数据
    const sortedOverrides = [...overrideShifts].sort((a, b) => a.start.getTime() - b.start.getTime());
    const result: Shift[] = [];
    let originalIdx = 0;
    let overrideIdx = 0;

    while (originalIdx < originalShifts.length && overrideIdx < sortedOverrides.length) {
        const currentOriginal = originalShifts[originalIdx];
        const currentOverride = sortedOverrides[overrideIdx];

        const origStart = currentOriginal.start.getTime();
        const origEnd = currentOriginal.end.getTime();
        const overStart = currentOverride.start.getTime();
        const overEnd = currentOverride.end.getTime();

        if (overStart >= origEnd) {
            // 覆盖班次在当前原班次之后，直接加入原班次
            result.push({...currentOriginal});
            originalIdx++;
        } else if (overEnd <= origStart) {
            // 覆盖班次在当前原班次之前，直接加入覆盖班次
            result.push({...currentOverride});
            overrideIdx++;
        } else {
            // 处理重叠区间
            if (origStart < overStart) {
                // 加入原班次未被覆盖的前半段
                result.push({
                    start: new Date(origStart),
                    end: new Date(overStart),
                    users: currentOriginal.users
                });
            }
            // 加入覆盖班次
            result.push({...currentOverride});

            if (overEnd >= origEnd) {
                // 覆盖班次完全覆盖当前原班次，原班次指针后移
                originalIdx++;
            } else {
                // 更新原班次起始时间，继续处理剩余部分
                currentOriginal.start = new Date(overEnd);
            }
            overrideIdx++;
        }
    }

    // 加入剩余的原班次
    while (originalIdx < originalShifts.length) {
        result.push({...originalShifts[originalIdx]});
        originalIdx++;
    }

    // 加入剩余的覆盖班次（若覆盖班次超出原班次时间范围）
    while (overrideIdx < sortedOverrides.length) {
        result.push({...sortedOverrides[overrideIdx]});
        overrideIdx++;
    }

    return result;
}

// 辅助函数：将示例字符串转为Date对象
function parseDate(dateStr: string): Date {
    const [day, month, year, hour, minute] = dateStr.split(/[- :]/).map(Number);
    return new Date(year, month - 1, day, hour, minute);
}

// 测试示例数据
const originalShifts = [
    {start: parseDate("01-07-2023 00:00"), end: parseDate("02-07-2023 00:00"), users: ['a']},
    {start: parseDate("02-07-2023 00:00"), end: parseDate("03-07-2023 00:00"), users: ['b']},
    {start: parseDate("03-07-2023 00:00"), end: parseDate("04-07-2023 00:00"), users: ['c']},
    {start: parseDate("04-07-2023 00:00"), end: parseDate("05-07-2023 00:00"), users: ['a']},
    {start: parseDate("05-07-2023 00:00"), end: parseDate("06-07-2023 00:00"), users: ['b']}
];

const overrideShifts = [
    {start: parseDate("01-07-2023 10:00"), end: parseDate("01-07-2023 15:00"), users: ['d']},
    {start: parseDate("04-07-2023 01:00"), end: parseDate("05-07-2023 12:00"), users: ['e']},
    {start: parseDate("02-07-2023 00:00"), end: parseDate("03-07-2023 00:00"), users: ['f']}
];

// 执行合并并输出结果
const mergedResult = mergeShifts(originalShifts, overrideShifts);
console.log(mergedResult.map(shift => ({
    start: shift.start.toLocaleString(),
    end: shift.end.toLocaleString(),
    users: shift.users
})));

复杂度分析 #

• 排序覆盖班次的时间复杂度：O(m log m)，其中m为覆盖班次数量
• 双指针遍历的时间复杂度：O(n + m)，其中n为原班次数量
• 整体时间复杂度：O(n + m log m)，适用于排班系统的常规数据量，性能高效

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