重叠时间区间算法？

Question

数据源：

       const TimeList = [
        {
          start_time: '2020-12-07',
          end_time: '2020-12-12',
          type: '1',
        },
        {
          start_time: '2020-12-13',
          end_time: '2021-04-16',
          type: '0',
        },
        {
          start_time: '2021-04-18',
          end_time: '2021-04-19',
          type: '1',
        },
      ]
      const LeaveTime = [
        {
          start_date: '2020-12-10',
          end_date: '2020-12-11',
          type: '3',
        },
        {
          start_date: '2020-12-18',
          end_date: '2020-12-22',
          type: '3',
        },
        {
          start_date: '2021-04-09', // 问题处在这里 没有去计算
          end_date: '2021-04-12',
          type: '3',
        },
        {
          start_date: '2021-04-15',
          end_date: '2021-04-17',
          type: '3',
        },
      ]

判断leaveTime里面的item项是否落在timeList里面，如果落在里面则以item的start_date作为节点进行重叠区域的切割，使之时间粒度更小。
以下是我写的，但是在2021-04-09部分就计算出错了

    <script src="https://cdn.bootcdn.net/ajax/libs/date-fns/2.0.0-alpha0/date_fns.js"></script>
    <script>
      /**
       * requestAnimationFrame polyfill
       */
      ;(function () {
        let lastTime = 0
        const vendors = ['ms', 'moz', 'webkit', 'o']
        for (
          let x = 0;
          x < vendors.length && !window.requestAnimationFrame;
          ++x
        ) {
          window.requestAnimationFrame =
            window[`${vendors[x]}RequestAnimationFrame`]
          window.cancelAnimationFrame =
            window[`${vendors[x]}CancelAnimationFrame`] ||
            window[`${vendors[x]}CancelRequestAnimationFrame`]
        }

        if (!window.requestAnimationFrame)
          window.requestAnimationFrame = function (callback) {
            const currTime = new DatePolyfill().getTime()
            const timeToCall = Math.max(0, 16 - (currTime - lastTime))
            const id = window.setTimeout(() => {
              callback(currTime + timeToCall)
            }, timeToCall)
            lastTime = currTime + timeToCall
            return id
          }

        if (!window.cancelAnimationFrame)
          window.cancelAnimationFrame = function (id) {
            clearTimeout(id)
          }

        class DatePolyfill {
          constructor(date) {
            if (!date) {
              return new Date()
            }
            const { userAgent } = window.navigator
            if (userAgent.includes('Safari') || userAgent.includes('wxwork')) {
              if (typeof date === 'string') {
                date = date.replace(/-/g, '/')
                return new Date(date)
              }
              return new Date(date)
            }
            return new Date(date)
          }
        }

        window.DatePolyfill = DatePolyfill
      })()
      const compareDate = function (d1, d2) {
        if (!d1 || !d2) {
          return false
        }
        if (typeof d1 === 'string') {
          d1 = new DatePolyfill(d1).getTime()
        }
        if (typeof d2 === 'string') {
          d2 = new DatePolyfill(d2).getTime()
        }
        return d1 > d2
      }
      const TimeList = [
        {
          start_time: '2020-12-07',
          end_time: '2020-12-12',
          type: '1',
        },
        {
          start_time: '2020-12-13',
          end_time: '2021-04-16',
          type: '0',
        },
        {
          start_time: '2021-04-18',
          end_time: '2021-04-19',
          type: '1',
        },
      ]
      const LeaveTime = [
        {
          start_date: '2020-12-10',
          end_date: '2020-12-11',
          type: '3',
        },
        {
          start_date: '2020-12-18',
          end_date: '2020-12-22',
          type: '3',
        },
        {
          start_date: '2021-04-09', // 问题处在这里 没有去计算
          end_date: '2021-04-12',
          type: '3',
        },
        {
          start_date: '2021-04-15',
          end_date: '2021-04-17',
          type: '3',
        },
      ]
      // b时间段是否在a的前面有交集
      const intersectionInFrontendTimeRange = (a, b) => {
        if (compareDate(a.start_date, b.start_date || b.start_time)) {
          return compareDate(b.end_date || b.end_time, a.start_date)
        }
        return false
      }
      const intersectionInBackendTimeRange = (a, b) => {
        if (compareDate(b.end_date || b.end_time, a.start_date)) {
          return compareDate(a.end_date, b.end_date || b.end_time)
        }
        return false
      }
      // 是否有时间交集
      const hasIntersectionTimeRange = (a, b) => {
        if (compareDate(b.start_date, a.start_date)) {
          return compareDate(b.end_date, a.start_date)
        }
        return compareDate(a.end_date, b.end_date)
      }
      // 是否是包含关系
      const isInTimeRange = (a, b) => {
        if (
          compareDate(b.start_date || b.start_time, a.start_date || a.start_time) ||
          a.start_date === b.start_date
        ) {
          return (
            compareDate(a.end_date || a.start_time, b.end_date || b.start_time) || a.end_date === b.end_date
          )
        }
        return false
      }
      const getNextDay = (dateString) =>
        dateFns.format(
          dateFns.addDays(new DatePolyfill(dateString), 1),
          'YYYY-MM-DD',
        )
      const getPrevDay = (dateString) =>
        dateFns.format(
          dateFns.addDays(new DatePolyfill(dateString), -1),
          'YYYY-MM-DD',
        )
      const timeArr = []
      TimeList.forEach((list) => {
        console.log('list', list);
        list.start_date = list.start_time;
        list.end_date = list.end_time;
        // 1. 和工作时间有交集的假期时间段
        const times = LeaveTime.filter(
          (item) => !!hasIntersectionTimeRange(list, item),
        )
        let currentTimeRange = list;
        if (times.length) {
            times.forEach((item, idx) => {
            console.log('times', item);
            // 总共处理三种情况
            // 存在包含关系
            // 存在交集的情况下，被假期时间包含的工作时间
            // 存在交集的情况下，被工作时间包含的假期时间
            // 不存在交集
            // 存在跨端关系
            //  工作时间后端有一段假期时间
            //  工作时间后端有一段假期时间
            // 被假期包含的工作时间
              console.log('timeArr: ',timeArr)

            debugger
            console.log('')
            if (!currentTimeRange) {
              return
            }
            if (isInTimeRange(item, currentTimeRange)) {
              if(!item.used) {
                debugger
              }
              if (item.used) {
                return
              }
              timeArr.push(item)
              item.used = true

              return
            }
            // 被工作时间包含的假期时间
            if (isInTimeRange(currentTimeRange, item)) {
              timeArr.push({
                start_time: currentTimeRange.start_date,
                end_time: getPrevDay(item.start_date),
                type: currentTimeRange.type,
              })
              if(item.used) {
                debugger
             }
              if (!item.used) {
                timeArr.push({
                  start_time: item.start_date,
                  end_time: item.end_date,
                  type: item.type,
                })
                item.used = true
              }
              currentTimeRange = {
                start_time: getNextDay(item.end_date),
                end_time: currentTimeRange.end_date,
                type: currentTimeRange.type,
              }
            } else {
                // debugger
              if (intersectionInBackendTimeRange(item, currentTimeRange)) {
                timeArr.push({
                  start_time: currentTimeRange.start_date || currentTimeRange.start_time,
                  end_time: getPrevDay(item.start_date),
                  type: currentTimeRange.type,
                })
                currentTimeRange = null
                if(item.used) {
                    debugger
                }
                if (!item.used) {
                  timeArr.push({
                    start_time: item.start_date,
                    end_time: item.end_date,
                    type: item.type,
                  })
                  item.used = true
                }
              } else if (
                intersectionInFrontendTimeRange(currentTimeRange, item)
              ) {
                if(item.used) {
                debugger
              }
                if (!item.used) {
                  timeArr.push({
                    start_time: item.start_date,
                    end_time: item.end_date,
                    type: item.type,
                  })
                  item.used = true
                }
                currentTimeRange = {
                  start_time: getNextDay(item.end_date),
                  end_time: currentTimeRange.end_date || currentTimeRange.end_time,
                  type: currentTimeRange.type,
                }
              }
            }
            // 1.5 把剩下的时间插进来
            if (idx === times.length - 1 && currentTimeRange) {
              timeArr.push(currentTimeRange)
            }
          })
        } else {
          timeArr.push(currentTimeRange)
        }
      })
    </script>

期望输出下面这种形式

[
        {
          start_date: '2020-12-07',
          end_date: '2020-12-09',
          type: '1',
        },
        {
          start_date: '2020-12-10',
          end_date: '2020-12-11',
          type: '3',
        },
        {
          start_date: '2020-12-12',
          end_date: '2020-12-12',
          type: '1',
        },
        {
          start_date: '2020-12-13',
          end_date: '2020-12-17',
          type: '0',
        },
        {
          start_date: '2021-12-08',
          end_date: '2021-12-22',
          type: '3',
        },
        {
          start_date: '2020-12-23',
          end_date: '2020-04-08',
          type: '0',
        },
        {
          start_date: '2021-04-09',
          end_date: '2021-04-12',
          type: '3',
        },
        {
          start_date: '2021-04-13',
          end_date: '2021-04-14',
          type: '0',
        },
        {
          start_date: '2020-04-15',
          end_date: '2020-04-17',
          type: '3',
        },
        {
          start_date: '2021-04-18',
          end_date: '2021-04-19',
          type: '1',
        },
      ]

Answer 1

type不知道干什么的，忽略。
timeList转换为数组并去重，得到类似const tag = [1,5,9,12,30]的结果
liveList应该保证顺序，类似const live = [[3,6],[7,9],[10,40]]的结果
如果tag中的值大于live中元素的第一个值且小于元素的最后一个值，将这个值插入元素的倒数第二位，重复执行到所有tag的值被遍历或tag的值大于live的最后一个元素的最后一个值为止。循环过程中为了效率，可以标记并调整live元素的处理起始位置，避免已处理的元素重复参与循环。
循环完成后得到 [[3,5,6],[7,9],[10,12,30,40]]的结果
每个item两两组合，最终为
[[3,5],[5,6],[7,9],[10,12],[12,30],[30,40]]
代码还是自己写吧，逻辑也就这样了。