按重叠日期范围分组数据的最优算法及实现咨询

该场景下最优解为扫描线算法，时间复杂度为O(n log n)，属于该问题的理论下界，输出结果和需求示例完全匹配。

核心思路 #

将每个日期区间拆分为「加入」和「移除」两个时间事件，按时间顺序遍历所有事件，动态维护当前区间内的活跃数据，遇到事件分界点时生成对应的结果区间即可。

实现步骤 #

• 生成事件列表：把每个输入对象拆成两个事件
  • 加入事件：时间为对象的start，操作为将name加入活跃数据集
  • 移除事件：时间为对象的end加1天，操作为将name从活跃数据集移除
• 事件排序：将所有事件按时间升序排列，相同时间的事件处理顺序不影响最终结果
• 遍历生成结果：
  • 初始化活跃数据集active、上一个事件时间lastTime、结果数组result
  • 逐个遍历排序后的事件：
    • 若lastTime存在且lastTime < 当前事件时间，且活跃数据集非空，就向结果数组插入区间：start = lastTime，end = 当前事件时间 - 1天，data为活跃数据集的副本
    • 处理当前事件的加入/移除操作
    • 更新lastTime为当前事件时间

代码示例（JavaScript） #

// 辅助函数：日期加1天，处理YYYY-MM-DD格式
function addOneDay(dateStr) {
  const date = new Date(dateStr);
  date.setDate(date.getDate() + 1);
  return date.toISOString().split('T')[0];
}

// 辅助函数：日期减1天
function subOneDay(dateStr) {
  const date = new Date(dateStr);
  date.setDate(date.getDate() - 1);
  return date.toISOString().split('T')[0];
}

function groupOverlappingDates(input) {
  const events = [];
  // 生成事件列表
  input.forEach(item => {
    events.push({ time: item.start, type: 'add', name: item.name });
    events.push({ time: addOneDay(item.end), type: 'remove', name: item.name });
  });
  // 按时间排序事件
  events.sort((a, b) => new Date(a.time) - new Date(b.time));
  
  const result = [];
  const active = [];
  let lastTime = null;
  
  for (const event of events) {
    const currTime = event.time;
    if (lastTime && lastTime < currTime && active.length > 0) {
      result.push({
        start: lastTime,
        end: subOneDay(currTime),
        data: [...active]
      });
    }
    // 处理事件
    if (event.type === 'add') {
      active.push(event.name);
    } else {
      const index = active.indexOf(event.name);
      if (index > -1) active.splice(index, 1);
    }
    lastTime = currTime;
  }
  return result;
}

// 测试用例
const input = [
  { start: '2021-10-01', end: '2022-10-01', name: 'data_1' },
  { start: '2021-11-01', end: '2022-02-01', name: 'data_2' },
  { start: '2021-12-01', end: '2022-01-01', name: 'data_3' }
];
console.log(groupOverlappingDates(input));

注意事项 #

• 日期加减要注意跨月、闰年问题，生产环境建议使用dayjs等成熟日期库处理
• 如果存在多个相同name的对象，可修改活跃数据集存储唯一标识而非直接存name，避免移除时误删

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