如何实现多人员可用时间范围的公共时段计算？

需求是找出所有人员可用时间的公共重叠时段，具体场景：

• 人员test的可用时间为上午10点至12点；
• 人员elton的可用时间为上午9点至10点30分、上午10点30分至11点；
• 人员shawn的可用时间为上午10点30分至11点；
  公共时段为上午10点30分至11点。

输入输出示例 #

示例1 #

输入：

const input = [
  {
    email: 'test@test.com',
    range: [
      {start: '10:00:00', end: '12:00:00' }
    ],
  },
  {
    email: 'elton@test.com',
    range: [
      {start: '09:00:00', end: '10:30:00'},
      {start: '10:30:00', end: '11:00:00' }
    ],
  },
  {
    email: 'shawn@test.com',
    range: [
      {start: '10:30:00', end: '11:00:00' }
    ],
  },
];

输出：

[
  {start: '10:30:00', end: '11:00:00' }
]

示例2 #

输入：

const input = [
  {
    email: 'test@test.com',
    range: [
      {start: '10:00:00', end: '12:00:00' }
    ],
  },
  {
    email: 'elton@test.com',
    range: [
      {start: '09:00:00', end: '10:30:00'},
      {start: '10:30:00', end: '11:00:00' },
      {start: '14:30:00', end: '15:00:00' }
    ],
  }
];

输出：

[
 {start: '10:00:00', end: '11:00:00' }
]

示例3 #

输入：

const input = [
  {
    email: 'test@test.com',
    range: [
      {start: '10:00:00', end: '12:00:00' },
      {start: '14:30:00', end: '15:00:00' }
    ],
  },
  {
    email: 'elton@test.com',
    range: [
      {start: '09:00:00', end: '10:30:00'},
      {start: '10:30:00', end: '11:00:00' },
      {start: '14:30:00', end: '15:00:00' }
    ],
  }
];

输出：

[
 {start: '10:00:00', end: '11:00:00' },
 {start: '14:30:00', end: '15:00:00' }
]

已尝试的代码 #

function generateIntersectSlot(interviewerRange) {
  if (!interviewerRange.length) {
    return [];
  }
  for (let interviewer of interviewerRange) {
    for (let nextInterviewer of interviewerRange) {
      if (interviewer.email == nextInterviewer.email) {
        continue;
      }
      console.log(interviewer.email, 'interviewerSlot email')
      console.log(nextInterviewer.email, 'nextInterviewer email')
      const interviewerSlot = interviewer.range;
      const nextInterviewerSlot = nextInterviewer.range;
      for (let intSlot of interviewerSlot) {
        for (let nextIntSlot of nextInterviewerSlot) {

          console.log(intSlot, 'intSlot')
          console.log(nextIntSlot, 'nextIntSlot')
          // if(new Date(`${getDate}T${intSlot.start}`) >= new Date(`${getDate}T${nextIntSlot.start}`) ) {
          //   console.log(intSlot, 'asd')
          // } else {

          // }


        }
      }
    }
  }
}

const input = [{
    email: 'test@test.com',
    range: [{
      start: '10:00:00',
      end: '12:00:00'
    }],
  },
  {
    email: 'elton@test.com',
    range: [{
        start: '09:00:00',
        end: '10:30:00'
      },
      {
        start: '10:30:00',
        end: '11:00:00'
      }
    ],
  },
  {
    email: 'shawn@test.com',
    range: [{
      start: '10:30:00',
      end: '11:00:00'
    }],
  },
];

generateIntersectSlot(input);

解决方案代码 #

// 将时间字符串转换为时间戳（毫秒），方便比较
function timeToTimestamp(timeStr) {
  const [hours, minutes, seconds] = timeStr.split(':').map(Number);
  return hours * 3600000 + minutes * 60000 + seconds * 1000;
}

// 将时间戳转换回时间字符串
function timestampToTime(timestamp) {
  const hours = Math.floor(timestamp / 3600000).toString().padStart(2, '0');
  const remaining = timestamp % 3600000;
  const minutes = Math.floor(remaining / 60000).toString().padStart(2, '0');
  const seconds = Math.floor((remaining % 60000) / 1000).toString().padStart(2, '0');
  return `${hours}:${minutes}:${seconds}`;
}

// 计算两个时间段数组的交集
function getIntersection(aRanges, bRanges) {
  const intersection = [];
  let aIndex = 0;
  let bIndex = 0;

  // 转换为时间戳格式的时间段，方便比较
  const aTimeRanges = aRanges.map(r => ({
    start: timeToTimestamp(r.start),
    end: timeToTimestamp(r.end)
  }));
  const bTimeRanges = bRanges.map(r => ({
    start: timeToTimestamp(r.start),
    end: timeToTimestamp(r.end)
  }));

  while (aIndex < aTimeRanges.length && bIndex < bTimeRanges.length) {
    const a = aTimeRanges[aIndex];
    const b = bTimeRanges[bIndex];

    // 计算重叠部分的起始和结束：起始取较大值，结束取较小值
    const start = Math.max(a.start, b.start);
    const end = Math.min(a.end, b.end);

    // 如果起始小于结束，说明有重叠，加入交集
    if (start < end) {
      intersection.push({
        start: timestampToTime(start),
        end: timestampToTime(end)
      });
    }

    // 移动指针：结束时间较小的时间段指针后移
    if (a.end < b.end) {
      aIndex++;
    } else {
      bIndex++;
    }
  }

  return intersection;
}

function generateIntersectSlot(interviewerRange) {
  if (!interviewerRange.length) {
    return [];
  }

  // 初始交集为第一个人的时间范围
  let currentIntersection = [...interviewerRange[0].range];

  // 依次和后面每个人的时间范围求交集
  for (let i = 1; i < interviewerRange.length; i++) {
    currentIntersection = getIntersection(currentIntersection, interviewerRange[i].range);
    // 如果交集为空，提前终止
    if (!currentIntersection.length) {
      break;
    }
  }

  return currentIntersection;
}

// 测试示例1
const input1 = [
  {
    email: 'test@test.com',
    range: [{start: '10:00:00', end: '12:00:00'}],
  },
  {
    email: 'elton@test.com',
    range: [{start: '09:00:00', end: '10:30:00'}, {start: '10:30:00', end: '11:00:00'}],
  },
  {
    email: 'shawn@test.com',
    range: [{start: '10:30:00', end: '11:00:00'}],
  },
];
console.log(generateIntersectSlot(input1)); // 输出：[{start: '10:30:00', end: '11:00:00'}]

// 测试示例2
const input2 = [
  {
    email: 'test@test.com',
    range: [{start: '10:00:00', end: '12:00:00'}],
  },
  {
    email: 'elton@test.com',
    range: [{start: '09:00:00', end: '10:30:00'}, {start: '10:30:00', end: '11:00:00'}, {start: '14:30:00', end: '15:00:00'}],
  }
];
console.log(generateIntersectSlot(input2)); // 输出：[{start: '10:00:00', end: '11:00:00'}]

// 测试示例3
const input3 = [
  {
    email: 'test@test.com',
    range: [{start: '10:00:00', end: '12:00:00'}, {start: '14:30:00', end: '15:00:00'}],
  },
  {
    email: 'elton@test.com',
    range: [{start: '09:00:00', end: '10:30:00'}, {start: '10:30:00', end: '11:00:00'}, {start: '14:30:00', end: '15:00:00'}],
  }
];
console.log(generateIntersectSlot(input3)); // 输出：[{start: '10:00:00', end: '11:00:00'}, {start: '14:30:00', end: '15:00:00'}]

代码说明 #

1. 时间转换函数：timeToTimestamp把时间字符串转成毫秒级时间戳，timestampToTime则反向转换，简化时间比较逻辑和结果输出。
2. 双指针求交集：遍历两个有序时间段数组，每次取当前两个时间段的最大起始值和最小结束值，若起始小于结束则为有效重叠时段；随后移动结束时间较小的时间段指针，继续遍历。
3. 逐步求公共交集：从第一个人的时间范围开始，依次与后续每个人的时间范围求交集，更新当前交集集合，直到遍历完所有人员或交集为空。

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