如何计算含起止日期的对象数组中重叠日期范围的最大数量

最优解法：扫描线算法 #

这个算法的时间复杂度为O(n log n)，是求解区间最大重叠数的标准最优方案，远优于暴力两两比对的*O(n²)*方案。

实现思路 #

• 把每个时间区间拆成两个事件：开始时间对应权重+1（表示新增一个重叠区间），结束时间对应权重-1（表示减少一个重叠区间）
• 对所有事件排序：优先按时间戳升序排列，若时间戳相同，默认把结束事件排在开始事件前，避免把「前一区间结束时间等于后一区间开始时间」的情况误判为重叠
• 遍历排序后的事件，实时统计当前重叠数，同步更新最大重叠数即可

代码实现 #

function getMaxOverlap(intervals) {
  // 生成事件数组
  const events = []
  intervals.forEach(interval => {
    const startTs = new Date(interval.start_date).getTime()
    const endTs = new Date(interval.end_date).getTime()
    events.push({ time: startTs, delta: 1 })
    events.push({ time: endTs, delta: -1 })
  })

  // 事件排序
  events.sort((a, b) => {
    if (a.time !== b.time) return a.time - b.time
    // 如需将「结束时间等于开始时间」判定为重叠，把下方返回值改为 b.delta - a.delta 即可
    return a.delta - b.delta
  })

  let currentOverlap = 0
  let maxOverlap = 0
  for (const event of events) {
    currentOverlap += event.delta
    maxOverlap = Math.max(maxOverlap, currentOverlap)
  }

  return maxOverlap
}

// 测试示例数据
const testData = [
  { start_date: '2021-01-01 10:00:00', end_date: '2021-01-01 11:00:00'},
  { start_date: '2021-01-01 08:00:00', end_date: '2021-01-01 11:00:00'},
  { start_date: '2021-01-01 12:00:00', end_date: '2021-01-01 14:00:00'},
  { start_date: '2021-01-01 12:30:00', end_date: '2021-01-01 14:30:00'},
  { start_date: '2021-01-01 14:00:00', end_date: '2021-01-01 17:30:00'},
]
console.log(getMaxOverlap(testData))
// 默认规则输出2，调整同时间排序优先级后输出3，匹配你提到的示例预期

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