时间段重合相关

Question

let arr = [
      { start: '2021-10-01', end: '2021-11-01' },
      { start: '2021-12-01', end: '2021-12-30' },
      { start: '2021-08-01', end: '2021-09-30' },
      { start: '2021-08-10', end: '2021-08-20' }
    ]

数组中有多个日期对象（开始时间和结束时间）想要快速判断（消耗低…）其中的日期是否有重合， 比如2021-08-10， 2021-08-20，是在arr[2]的时间范围内，已经重合… 该用哪种方式判断比较好

Answer 1

这个有很多方法，要效率高，还有用空间换时间的方法。
比如可以构建一个日期对应的set集合，每个时间段都会让set的某个连续区域被设置，在新区域来的时候，就先检查对应区域是否已经有被设置的，有就有重叠啦，否则就进行设置。

比如这数组中的日期段是在一年以内，则用366bit的set就可以进行全部标注，每个日期段都可以映射到某位中，当然，这个只对于日期不是太长的比较方便。

另外一种其实也是只需要依次遍历，而不需要提前排序，而是边插入边排序，比如构造一个单向链表类似的结构，每次新时间段来，如果能够插入到合适的位置，则插入，否则就是存在重叠啦，这个判断依据就是：

1. 新时间段c的开始时间是原链表中某个节点a结束时间之后
2. 新时间段c的结束时间是原链表中某个节点a的下一节点b开始时间之前

既 Ea<Sc<Ec<Sb 为可以插入，否则有重叠。

Answer 2

如果是给一个新的时间段，判断是否和数组里已有的重合，那就遍历一遍就好了。

如果有很多，那可能要先排序，减少查找次数。

Answer 3

const findRepeatTime = (arr) => {
  let timeRange = [];
  arr.sort((a, b) => new Date(a.start).getTime() - new Date(b.start).getTime());
  arr.map((time, index) => {
    const timeRangeLen = timeRange.length;
    if (index === 0 || new Date(timeRange[timeRangeLen - 1].end).getTime() < new Date(time.start).getTime()) {
      timeRange.push(time);
      time.repeat = false;
    } else if (new Date(timeRange[timeRangeLen - 1].end).getTime() < new Date(time.end).getTime()) {
      timeRange[timeRangeLen - 1].end = time.end;
      time.repeat = true;
      arr[index - 1].repeat = true;
    } else {
      time.repeat = true;
      arr[index - 1].repeat = true;
    }
  });
  return arr;
};
console.log(
  findRepeatTime([
    { start: '2021-10-01', end: '2021-11-01' },
    { start: '2021-12-01', end: '2021-12-30' },
    { start: '2021-08-01', end: '2021-09-30' },
    { start: '2021-08-10', end: '2021-08-20' },
    { start: '2021-12-02', end: '2021-12-10' },
    { start: '2021-12-11', end: '2021-12-12' },
  ])
);

结果:

[
  {start: '2021-08-01', end: '2021-09-30', repeat: true},
  {start: '2021-08-10', end: '2021-08-20', repeat: true},
  {start: '2021-10-01', end: '2021-11-01', repeat: false},
  {start: '2021-12-01', end: '2021-12-30', repeat: true},
  {start: '2021-12-02', end: '2021-12-10', repeat: true},
  {start: '2021-12-11', end: '2021-12-12', repeat: true}
]

Answer 4

题主这个需求说得不是很明白，判断重合，然后呢？

如果单纯的只是想把被其他时间合并的那些时间段找出来，比如 { start: '2021-08-10', end: '2021-08-20' } 这条，那就是双重遍历

function isIn(value, another) {
    return value.start >= another.start && value.end <= another.end;
}

const contained = arr.filter(value => arr.some(another => value !== another && isIn(value, another)));

如果是想过滤掉，上面 filter 中的判定条件取反就好。

如果是想合并时间范围，那就会复杂一些，不仅要判断重复，还要判断交叉（部分重复）