如何实现日程空闲时段有效性验证算法（JS/Go）

问题描述 #

给定一组无重叠且已按开始时间排序的忙碌时间区间（毫秒时间戳），验证待新增的时段是否可以安排（即与所有已有区间无重叠）。

核心思路 #

因为区间已按开始时间升序排列，我们可以用二分查找快速定位可能冲突的区间，将时间复杂度从线性遍历的O(n)优化到O(log n)，适合处理大规模区间场景。

冲突判定规则：
新增时段 [inc.start, inc.end] 与某区间 [slot.start, slot.end] 冲突的条件是：
inc.start < slot.end && inc.end > slot.start
反之，只要新增时段与所有区间都不满足该条件，即可安排。

需覆盖的边缘情况：

• 忙碌区间列表为空
• 新增时段完全在所有区间之前/之后
• 新增时段与已有区间刚好相邻（如新增时段结束时间等于某区间开始时间）
• 新增时段的开始时间等于结束时间（无时长，视为可安排）
• 新增时段开始时间大于结束时间（参数非法，返回false）

JavaScript 实现 #

const timeslots = [
  { start: 10, end: 14 },
  { start: 17, end: 21 },
  { start: 30, end: 37 },
  // ... 可添加更多区间
];
// 确保区间按开始时间升序排列（若输入未排序，此步骤必须执行）
const sortedSlots = timeslots.sort((a, b) => a.start - b.start);

const checkValid = (inc) => {
  // 参数合法性校验
  if (typeof inc.start !== 'number' || typeof inc.end !== 'number' || inc.start > inc.end) {
    return false;
  }
  // 空区间列表直接返回可安排
  if (sortedSlots.length === 0) {
    return true;
  }

  let left = 0;
  let right = sortedSlots.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const current = sortedSlots[mid];

    // 检查当前区间是否与新增时段冲突
    if (inc.start < current.end && inc.end > current.start) {
      return false;
    }

    // 新增时段在当前区间左侧，去左半区排查
    if (inc.end <= current.start) {
      right = mid - 1;
    } else {
      // 新增时段在当前区间右侧，去右半区排查
      left = mid + 1;
    }
  }

  // 遍历完所有可能区间，无冲突
  return true;
};

// 测试用例
console.log(checkValid({ start: 15, end: 16 })); // true（无重叠）
console.log(checkValid({ start: 15, end: 18 })); // false（与[17,21]重叠）
console.log(checkValid({ start: 16, end: 27 })); // false（与[17,21]重叠）
console.log(checkValid({ start: 8, end: 39 })); // false（覆盖多个区间）
// 边缘情况测试
console.log(checkValid({ start: 14, end: 17 })); // true（刚好相邻）
console.log(checkValid({ start: 0, end: 9 })); // true（在所有区间之前）
console.log(checkValid({ start: 38, end: 40 })); // true（在所有区间之后）
console.log(checkValid({ start: 21, end: 30 })); // true（区间间隙）
console.log(checkValid({ start: 5, end: 5 })); // true（无时长）
console.log(checkValid({ start: 20, end: 15 })); // false（参数非法）

Go 实现 #

package main

import (
	"fmt"
	"sort"
)

// Slot 定义时间区间结构
type Slot struct {
	Start int64
	End   int64
}

// CheckValid 验证新增时段是否可安排
func CheckValid(sortedSlots []Slot, inc Slot) bool {
	// 参数合法性校验
	if inc.Start > inc.End {
		return false
	}
	if len(sortedSlots) == 0 {
		return true
	}

	left, right := 0, len(sortedSlots)-1
	for left <= right {
		mid := (left + right) / 2
		current := sortedSlots[mid]

		// 检查冲突
		if inc.Start < current.End && inc.End > current.Start {
			return false
		}

		if inc.End <= current.Start {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return true
}

func main() {
	timeslots := []Slot{
		{Start: 10, End: 14},
		{Start: 17, End: 21},
		{Start: 30, End: 37},
	}
	// 确保区间排序（若输入未排序）
	sort.Slice(timeslots, func(i, j int) bool {
		return timeslots[i].Start < timeslots[j].Start
	})

	// 测试用例
	fmt.Println(CheckValid(timeslots, Slot{15, 16}))  // true
	fmt.Println(CheckValid(timeslots, Slot{15, 18}))  // false
	fmt.Println(CheckValid(timeslots, Slot{16, 27}))  // false
	fmt.Println(CheckValid(timeslots, Slot{8, 39}))   // false
	fmt.Println(CheckValid(timeslots, Slot{14, 17}))  // true
	fmt.Println(CheckValid(timeslots, Slot{0, 9}))    // true
	fmt.Println(CheckValid(timeslots, Slot{38, 40}))  // true
	fmt.Println(CheckValid(timeslots, Slot{21, 30}))  // true
	fmt.Println(CheckValid(timeslots, Slot{5, 5}))    // true
	fmt.Println(CheckValid(timeslots, Slot{20, 15}))  // false
}

内容的提问来源于stack exchange，提问作者P A S H