JavaScript 检查时间范围是否重叠

Question

我有例如一个包含 2 个对象的数组(myObject1 和 myObject2，如 )。现在，当我添加第三个对象时，我将检查时间范围是否重叠。实际上我不知道如何以高效的方式做到这一点。

var myObjectArray = [];

var myObject1 = {};
myObject1.startTime = '08:00';
myObject1.endTime = '12:30';
...

var myObject2 = {};
myObject2.startTime = '11:20';
myObject2.endTime = '18:30';
...

myObjectArray.push(myObject1);
myObjectArray.push(myObject2);

Answer 1

假设我们有一些间隔

const INTERVALS = [
  ['14:00', '15:00'],
  ['08:00', '12:30'],
  ['12:35', '12:36'],
  ['13:35', '13:50'],
];

如果我们想向这个列表中添加新的间隔，我们应该检查新的间隔是否与其中的一些不重叠。

您可以遍历间隔并检查新间隔是否与其他间隔重叠。请注意，在比较时间间隔时，如果您确定日期是同一天，则不需要 Date 对象，因为您可以将时间转换为数字:

function convertTimeToNumber(time) {
  const hours = Number(time.split(':')[0]);
  const minutes = Number(time.split(':')[1]) / 60;
  return hours + minutes;
}

有两种区间不重叠的情况:

1. 在 (a < c && a < d) && (b < c && b

a          b
|----------|
             c          d
             |----------| 

1. 在 (a > c && a > d) && (b > c && b > d) 之后:

             a          b
             |----------|
c          d
|----------| 

因为总是c < d , 足以说明不重叠区间的条件是 (a < c && b < c) || (a > d && b > d)因为总是 a < b ，只要说这个条件等同于:

b < c || a > d

这个条件的否定应该给我们一个重叠区间的条件。基于De Morgan's laws它是:

b >= c && a <= d

请注意，在这两种情况下，间隔不能相互“接触”，这意味着 5:00-8:00 和 8:00-9:00 会重叠。如果你想允许它，条件应该是:

b > c && a < d

至少有5种区间重叠的情况需要考虑:

a          b
|----------|
      c          d
      |----------| 

      a          b
      |----------|
c          d
|----------| 

      a          b
      |----------|
c                    d
|--------------------|

a                    b
|--------------------|
      c          d
      |----------|

a          b
|----------|
c          d
|----------|

带有额外添加和排序间隔函数的完整代码如下:

    const INTERVALS = [
      ['14:00', '15:00'],
      ['08:00', '12:30'],
      ['12:35', '12:36'],
      ['13:35', '13:50'],
    ];


    function convertTimeToNumber(time) {
      const hours = Number(time.split(':')[0]);
      const minutes = Number(time.split(':')[1]) / 60;
      return hours + minutes;
    }

    // assuming current intervals do not overlap
    function sortIntervals(intervals) {
      return intervals.sort((intA, intB) => {
        const startA = convertTimeToNumber(intA[0]);
        const endA = convertTimeToNumber(intA[1]);

        const startB = convertTimeToNumber(intB[0]);
        const endB = convertTimeToNumber(intB[1]);

        if (startA > endB) {
          return 1
        }

        if (startB > endA) {
          return -1
        }

        return 0;
      })
    }


    function isOverlapping(intervals, newInterval) {
      const a = convertTimeToNumber(newInterval[0]);
      const b = convertTimeToNumber(newInterval[1]);

      for (const interval of intervals) {
        const c = convertTimeToNumber(interval[0]);
        const d = convertTimeToNumber(interval[1]);

        if (a < d && b > c) {
          console.log('This one overlap: ', newInterval);
          console.log('with interval: ', interval);
          console.log('----');
          return true;
        }
      }

      return false;
    }

    function isGoodInterval(interval) {
      let good = false;

      if (interval.length === 2) {
        // If you want you can also do extra check if this is the same day
        const start = convertTimeToNumber(interval[0]);
        const end = convertTimeToNumber(interval[1]);

        if (start < end) {
          good = true;
        }
      }

      return good;
    }

    function addInterval(interval) {
      if (!isGoodInterval(interval)) {
        console.log('This is not an interval');
        return;
      }

      if (!isOverlapping(INTERVALS, interval)) {
        INTERVALS.push(interval);

        // you may also want to keep those intervals sorted
        const sortedIntervals = sortIntervals(INTERVALS);
        console.log('Sorted intervals', sortedIntervals);
      }
    }


    // --------------------------------------
    const goodIntervals = [
      ['05:31', '06:32'],
      ['16:00', '17:00'],
      ['12:31', '12:34']
    ];

    let goodCount = 0;
    for (const goodInterval of goodIntervals) {
      if (!isOverlapping(INTERVALS, goodInterval)) {
        goodCount += 1
      }
    }

    console.log('Check good intervals: ', goodCount === goodIntervals.length);

    // --------------------------------------
    const ovelappingIntervals = [
      ['09:30', '12:40'],
      ['05:36', '08:50'],
      ['13:36', '13:37'],
      ['06:00', '20:00'],
      ['14:00', '15:00']
    ]

    let badCount = 0;
    for (const badInterval of ovelappingIntervals) {
      if (isOverlapping(INTERVALS, badInterval)) {
        badCount += 1
      }
    }

    console.log('Check bad intervals: ', badCount === ovelappingIntervals.length);

    // --------------------------------------
    addInterval(goodIntervals[0])