如何用JavaScript验证时间线数组重叠并修正序号计算逻辑？

问题需求 #

检查timelineArray中的时间线是否重叠：

• 存在重叠时，基于所有重叠项的increment累加生成序号区间
• 无重叠时，序号从1开始

原始timelineArray #

var timelineArray = [
  ["name1", "384", "456", "30"],
  ["name2", "72", "192", "30"],
  ["name3", "384", "456", "30"],
  ["name4", "384", "456", "15"],
  ["name5", "384", "576", "30"],
  ["name6", "96", "240", "12"],
  ["name7", "384", "456", "12"],
  ["name8", "1", "3", "12"]
];

当前代码 #

function checkTimelineOverlap(timelineArray) {
  let result = [];
  let currentStart = 1;
  let currentEnd = 0;
  let lastIncrement = 0; // Initialize lastIncrement to 0

  for (let i = 0; i < timelineArray.length; i++) {
    const [name, start, end, increment] = timelineArray[i];
    startNum = parseInt(start);
    endNum = parseInt(end);
    incrementNum = parseInt(increment);

    let overlapNames = [];
    for (let j = 0; j < i; j++) {
      const [prevName, prevStart, prevEnd, prevIncrement] = timelineArray[j]; // Add prevIncrement here
      if (
        (startNum >= parseInt(prevStart) && startNum <= parseInt(prevEnd)) ||
        (endNum >= parseInt(prevStart) && endNum <= parseInt(prevEnd)) ||
        (startNum <= parseInt(prevStart) && endNum >= parseInt(prevEnd))
      ) {
        overlapNames.push(prevName);
        lastIncrement = parseInt(prevIncrement); // Store the increment value of the last overlapping event
      }
    }

    let overlapMessage =
      overlapNames.length > 0 ? `overlap with ${overlapNames.join(", ")}` : "no overlap";

    if (overlapNames.length > 0) {
      currentEnd += lastIncrement; // Use the lastIncrement to update currentEnd
      currentStart = lastIncrement + 1;
    } else {
      // Update both currentStart and currentEnd when there's no overlap
      currentStart = 1;
      currentEnd = currentStart + incrementNum - 1;
    }

    result.push(`${name}, ${overlapMessage}, ${currentStart}-${currentEnd}`);

    // Reset lastIncrement for the next iteration
    lastIncrement = 0;
  }

  return result;
}

var timelineArray = [
  ["name1", "384", "456", "30"],
  ["name2", "72", "192", "30"],
  ["name3", "384", "456", "30"],
  ["name4", "384", "456", "15"],
  ["name5", "384", "576", "30"],
  ["name6", "96", "240", "12"],
  ["name7", "384", "456", "12"],
  ["name8", "1", "3", "12"]
];

const result = checkTimelineOverlap(timelineArray);
console.log(result);

当前输出 #

1. name1, no overlap, 1-30
2. name2, no overlap, 1-30
3. name3, overlap with name1, 31-60
4. name4, overlap with name1, name3, 31-90
5. name5, overlap with name1, name3, name4, 16-105
6. name6, overlap with name2, 31-135
7. name7, overlap with name1, name3, name4, name5, 31-165
8. name8, no overlap, 1-12

预期输出 #

1. name1, no overlap, 1-30
2. name2, no overlap, 1-30
3. name3, overlap with name1, 31-60
4. name4, overlap with name1 and name3 , 61-75
5. name5, overlap with name1,name3 and name4, 76-105
6. name6, overlap with name2, 31-42
7. name7, overlap with name1,name3,name4 and name5, 106-118
8. name8, no overlap, 1-12

修正后的代码及解释 #

问题分析 #

原代码核心问题：

1. 仅记录最后一个重叠项的increment，未累加所有重叠项的总长度
2. 未按时间线分组维护区间，导致不同时间线组的区间混乱
3. 重叠消息格式不符合预期（多个重叠项时未用"and"连接最后一项）

修正代码 #

function checkTimelineOverlap(timelineArray) {
  const result = [];
  // 存储每个时间线组的最大结束序号，key为时间线的start-end范围标识
  const timelineGroups = new Map();

  for (let i = 0; i < timelineArray.length; i++) {
    const [name, startStr, endStr, incrementStr] = timelineArray[i];
    const start = parseInt(startStr);
    const end = parseInt(endStr);
    const increment = parseInt(incrementStr);

    // 收集重叠项并找到对应组的最大结束序号
    const overlapNames = [];
    let maxEnd = 0;
    for (let j = 0; j < i; j++) {
      const [prevName, prevStartStr, prevEndStr] = timelineArray[j];
      const prevStart = parseInt(prevStartStr);
      const prevEnd = parseInt(prevEndStr);
      // 判断时间线重叠逻辑
      const isOverlap = (start >= prevStart && start <= prevEnd) || 
                        (end >= prevStart && end <= prevEnd) || 
                        (start <= prevStart && end >= prevEnd);
      if (isOverlap) {
        overlapNames.push(prevName);
        // 更新当前项对应的最大结束序号
        const groupKey = `${prevStart}-${prevEnd}`;
        if (timelineGroups.has(groupKey)) {
          const groupEnd = timelineGroups.get(groupKey);
          maxEnd = Math.max(maxEnd, groupEnd);
        }
      }
    }

    // 生成符合要求的重叠消息
    let overlapMessage = "no overlap";
    if (overlapNames.length > 0) {
      if (overlapNames.length === 1) {
        overlapMessage = `overlap with ${overlapNames[0]}`;
      } else {
        const lastItem = overlapNames.pop();
        overlapMessage = `overlap with ${overlapNames.join(",")} and ${lastItem}`;
        overlapNames.push(lastItem); // 恢复原数组
      }
    }

    // 计算当前项的序号区间
    let currentStart, currentEnd;
    if (overlapNames.length > 0) {
      currentStart = maxEnd + 1;
      currentEnd = currentStart + increment - 1;
    } else {
      currentStart = 1;
      currentEnd = currentStart + increment - 1;
    }

    // 更新当前时间线组的最大结束序号
    const currentGroupKey = `${start}-${end}`;
    timelineGroups.set(currentGroupKey, currentEnd);

    result.push(`${i + 1}. ${name}, ${overlapMessage}, ${currentStart}-${currentEnd}`);
  }

  return result;
}

// 测试执行
var timelineArray = [
  ["name1", "384", "456", "30"],
  ["name2", "72", "192", "30"],
  ["name3", "384", "456", "30"],
  ["name4", "384", "456", "15"],
  ["name5", "384", "576", "30"],
  ["name6", "96", "240", "12"],
  ["name7", "384", "456", "12"],
  ["name8", "1", "3", "12"]
];

const result = checkTimelineOverlap(timelineArray);
result.forEach(item => console.log(item));

关键改进点 #

1. 分组维护区间：用Map存储每个时间线范围的最大结束序号，确保不同时间线组的区间独立计算
2. 累加重叠项总长度：找到当前项所有重叠项组的最大结束序号，以此为基础生成当前区间
3. 优化消息格式：处理多个重叠项时，最后一项前用"and"连接，匹配预期输出
4. 修正变量作用域：将解析后的变量改为块级作用域，避免全局污染

来源说明 #

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