时间段内不重叠配置处理
这是一个业务需求的实现问题，感觉要思考一下，所以记录下来。
需求简述
要支持一天 24 小时内的不重叠时间段配置，步长为半小时，比如可以同时配置如下时间段：
js
// 同时有如下配置
00:00-12:00 // ✅
12:00-18:00 // ✅
19:30-24:00 // ✅但是下面这样是不支持的：
js
// 同时有如下配置
00:00-12:00 // ✅
10:30-20:00 // ❌ 因为这里和前面的时间段有重叠，重叠部分是 10:30-12:00
20:00-20:00 // ❌ 因为必须配置为时间段，不能是时间点需求详述
这实际上是一个后管配置页面的需求，支持使用时间段的选择。
这里讨论的重点是实现逻辑，样式方面的 UI 和具体前端框架可以忽略。
配置逻辑要求如下：
- 这是一个动态表单，由 n 个结构相同的配置项组成，n 最少为 1
- 这个表单每一项里面，要配置一个时间段，时间段的要求是：
- 时间段包含一个
起始时间和一个结束时间 起始时间早于结束时间起始时间需要为整点或半点，即假设在 7 点这个时段内，起始时间可以是 7:30，也可以是 7:00，但不可以是 7:01 或者 7:59起始时间和结束时间的步长为半小时，且最少间隔半小时，结束时间为起始时间 + n 个半小时，所以结束时间也为整点或半点。即假设起始时间为 14:00，则结束时间为 14:30，15:00，15:30……以此类推都是合法的（假设只有这一个配置项的情况下）- 时间段不需要跨天，不需要考虑 23:00 - 1:00 的情况
- 时间段包含一个
- 配置项之间的时间段不能重合，即如果配置了 1:00 - 2:00，则配置 1:00 - 3:00 或者 1:30 - 2:30 都是不合法的
分析问题
这个第一反应确实不知道该找什么算法来处理，但是抽象来看，这是一个查找和编辑区间的场景，对于处理时间段不重叠的问题，可以考虑下区间树（Interval Tree）。
区间树是一种特别适合于区间重叠检测的数据结构。它允许快速查找任何与给定区间重叠的区间。每个节点维护着它的最大端点值，这可以用来快速排除不重叠的区间，从而高效地执行查询和插入操作。
区间树是基于红黑树实现的，然而大学的算法课，我好像没有好好学习红黑树（不知道是老师没有讲还是我忘了），看起来要补的课还不少。并且构建树在这个场景下收益可能并不高，一方面是查找的频率并不高，并且构建树的成本也不低。
为了确保业务需求的优先级，不如再看看有没有更简单的实现方式。
既然这里都是时间段，是不是可以考虑用一个数组，来模拟时间段进行实现，比如：
原时间段: |--00:00～00:30--|--00:30～01:00--|--01:00～01:30--|……|--23:30～24:00--|
线段映射: |---------0--------|---------1--------|---------2-------|……|--------47--------| （线段映射这里是为了方便理解，实际设计上不含这个层级）
数组表示: [0, 1, 2, ..., 47]
也就是说，在最后的数组表示中：
- 0 代表 0 点到 0 点 30 分这半个小时
- 1 代表 0 点 30 分到 1 点这半小时
- 以此类推……
- 最后的 47 表示 23 点 30 分到 24 点整
当我需要表示 0 点到 3 点这个时间段被占用时，它们的表示状态分别为：
原时间段：['00:00', '03:00'] 数组表示: [0, 6]， 如果是要表示12 点 30 分到 14 点这个时间段被占用，它们的表示状态分别为： 原时间段：['12:30', '14:00'] 数组表示: [25, 28]，
于是我决定分 2 个层级的类来实现，一个是上层的映射胶水层，另一个是底层的核心层。他们的作用分别是：
- 核心层：只关注数组的中每一位的占用状态的维护和查询，确保每次操作都有一个显式的状态返回，比如想表示第 0 个线段被占用时，调用插入方法，能知道插入是否成功，如果失败，是因为谁占用而导致了失败。因为时间块可能是多段并用的，也就是说，可能是有一个人一次性占用了0 到 10 这 10 个 30 分钟的时间块。
- 映射胶水层：只关注将 0、1、2 等这些转换成具体的时间，也就是说，当有一个表示占用时间的段[0, 10]，这个层级需要能够正确地转换成时间段['00:00', '05:00']，表示这个连续的时间段被占用
代码实现
核心层
javascript
// SegmentListUtilBase.js
/**
* @typedef {Object} isSegmentUsedReturn
* @property {boolean} isSegmentUsed 区间是否已经被使用
* @property {Array<[number, number]>} [usedSegmentList=[]] 被使用的区间列表
*/
/**
* @class
* @classdesc 如果你需要一个工具，来帮你维护一个时间段内多个时间切片的占用情况，可以考虑基于这个类，封装一层适合业务的胶水层。
* @example
* // 假设有一个业务场景，一天内分为24个小时，需要维护每个小时占用的情况，可以这样用：
* const segmentListUtilBase = new SegmentListUtilBase(24)
* // 此时用一个长度为24的数组来代表这一天内的时间段
* // |00:00-01:00|01:00-02:00|...|23:00-24:00|
*
* // 此时我们用[0, 0]来表示00:00-01:00被占用了，可以用如下代码表示。其中 isSuccess 表示是否能插入成功，usedSegmentList 表示如果失败，是因为被哪些时间段被占用导致插入失败
* let { isSuccess, usedSegmentList } = segmentListUtilBase.addSegment(0, 0) // isSuccess 为 true, usedSegmentList为 []
*
* // 如果此时我们还想在分别插入 02:00-04:00、 03:00-07:00 两个时间段，则有:
* { isSuccess, usedSegmentList } = segmentListUtilBase.addSegment(2, 3) // isSuccess 为 true, usedSegmentList为 []
* { isSuccess, usedSegmentList } = segmentListUtilBase.addSegment(3, 6) // isSuccess 为 false, usedSegmentList为 [[2, 3]]
* // 当你拿到[2, 3]后，基于你自己的胶水层，实现对区间块编号和时间段之间的转换，可以将[2, 3]转换为表示 02:00-04:00 的时间段，比如写下面2个类似的胶水方法：
*
* // 将时间块编号转换为"mm:ss"时间字符串
* indexToTime(index) {
* const step = 60 // 一小时60分钟
* const totalMinutes = index * step; // 距离0点，经过了多少分钟
*
* const hours = Math.floor(totalMinutes / 60); // 计算出一共有多少小时
* const minutes = totalMinutes % 60; // 计算出余下多少分钟
*
* const hoursStr = `00${hours}`.slice(-2); // 获得小时的文本
* const minutesStr = `00${minutes}`.slice(-2); // 获得分钟的文本
*
* return `${hoursStr}:${minutesStr}`; // 返回格式为"mm:ss"的字符串
* }
*
* // 将"mm:ss"时间字符串转为时间块的编号
* timeToSegment(timeText, step = 60) {
* const timeReg = /^(((([0-1]?\d)|(2[0-3])):([0-5]?\d))|(24:00))$/g; // 校验传入的时间格式是否正确
*
* if (!timeReg.test(timeText)) {
* throw new Error("传入的时间格式不正确，其范围范围为 00:00 - 24:00");
* } else {
* const [hoursStr, minutesStr] = timeText.split(":");
* const hours = Number.parseInt(hoursStr);
* const minutes = Number.parseInt(minutesStr);
*
* return Math.floor(hours * (60 / step)) + Math.floor(minutes / step);
* }
* }
* // index表示在某个时间段的节点，比如起始时间为02:00结束时间为04:00，传入indexToTime(2)会得到文本"02:00"，再传入indexToTime(4)得到时间点"04:00"
*/
class SegmentListUtilBase {
_segmentList = [];
/**
* 用来表示已占用的区间块的map映射
* @type {undefined | Map}
* @private
*/
_usedSegmentMap = undefined;
/**
* @constructor
* @param {number} length 要构建的区间长度
*/
constructor(length) {
if (length <= 0) {
throw new Error("length 参数必须为正整数");
}
this._initSegmentList(length);
this._usedSegmentMap = new Map();
}
/**
* 对 {@link _segmentList} 初始化一个长度为 {@link length} 并用 null 填充的数组
* @private
* @param {number} length 初始化的区间长度
*/
_initSegmentList(length) {
this._segmentList.length = length;
this._segmentList.fill(null);
}
/**
* 校验提供的区间是否合法
* @private
* @param {number} startSegmentNum 起始的区间编号
* @param {number} endSegmentNum 结束的区间编号
*/
_validateSegment(startSegmentNum, endSegmentNum) {
if (startSegmentNum == null || endSegmentNum == null) {
throw new Error("参数 startSegmentNum 和 endSegmentNum 均必传");
}
if (startSegmentNum > endSegmentNum) {
throw new Error("startSegmentNum 参数必须小于或等于 endSegmentNum");
}
this._validateOutOfRange(startSegmentNum, endSegmentNum);
}
/**
* 校验提供的区间编号是否超出当前实体对象允许的区间
* @private
* @param {number} startSegmentNum 起始的区间编号
* @param {number} endSegmentNum 结束的区间编号
*/
_validateOutOfRange(startSegmentNum, endSegmentNum) {
if (
startSegmentNum >= this._segmentList.length ||
endSegmentNum >= this._segmentList.length
) {
throw new Error(
`[${startSegmentNum}, ${endSegmentNum}] 区间超出范围`,
);
}
}
/**
* 将给定到区间[startSegmentNum, endSegmentNum]数组作为元素，插值更新{@link _segmentList}数组中的第{@link startSegmentNum}到第{@link endSegmentNum}每一位
* @param {number} startSegmentNum 起始的区间编号
* @param {number} endSegmentNum 结束的区间编号
* @param {*} [updateContent=false] 使用该值填充到{@link _segmentList}数组中，建议不要轻易修改，增加这个值只为了方便实现{@link removeSegment}方法，通过填充 null 实现“逻辑删除”
*/
_updateSegmentList(startSegmentNum, endSegmentNum, updateContent = false) {
for (let i = startSegmentNum; i <= endSegmentNum; i++) {
if (updateContent === false) {
this._segmentList[i] = [startSegmentNum, endSegmentNum];
} else {
this._segmentList[i] = updateContent;
}
}
}
/**
* 判断给定的区间 [start, end] 是否已经被使用了
* @param {number} startSegmentNum 需要检查的起始的区间编号
* @param {number} endSegmentNum 需要检查的结束的区间编号
* @returns {isSegmentUsedReturn}
*/
isSegmentUsed(startSegmentNum, endSegmentNum) {
let isSegmentUsed = false;
const set = new Set();
for (let i = startSegmentNum; i <= endSegmentNum; i++) {
const segment = this._segmentList[i];
if (segment !== null && segment !== undefined) {
isSegmentUsed = true;
set.add(JSON.stringify(segment));
}
}
return {
isSegmentUsed,
usedSegmentList: Array.from(set).map((segmentStr) =>
JSON.parse(segmentStr),
),
};
}
/**
* 根据给定的区间 [startSegmentNum, endSegmentNum] 尝试插入，成功与否通过返回的对象中的 {@link isSuccess} 布尔值参数进行反馈，如果失败会返回占用的区间段
* @param {number} startSegmentNum 需要插入的起始的区间编号
* @param {number} endSegmentNum 需要插入的结束的区间编号
* @returns {isSegmentUsedReturn}
*/
addSegment(startSegmentNum, endSegmentNum) {
this._validateSegment(startSegmentNum, endSegmentNum);
const { isSegmentUsed, usedSegmentList } = this.isSegmentUsed(
startSegmentNum,
endSegmentNum,
);
if (!isSegmentUsed) {
this._updateSegmentList(startSegmentNum, endSegmentNum);
this._usedSegmentMap.set(
JSON.stringify([startSegmentNum, endSegmentNum]),
[startSegmentNum, endSegmentNum],
);
}
return {
isSuccess: !isSegmentUsed,
usedSegmentList: isSegmentUsed ? usedSegmentList : undefined,
};
}
/**
* 根据给定的区间 [startSegmentNum, endSegmentNum] 尝试删除，如果传入的区间涉及到已有区间，则会把删掉的区间列表返回。
* @example
* // 假设要删除区间[2, 10]，而已占用的区间有[1,3],[4,6],[9,12],[13,16]
* const usedSegmentList = removeSegment(2, 10)
* // 则 usedSegmentList 的值为：
* [[1, 3], [4, 6], [9, 12]]
* @param {number} startSegmentNum 需要删除的起始的区间编号
* @param {number} endSegmentNum 需要删除的结束的区间编号
* @returns {Array<[number, number]>}
*/
removeSegment(startSegmentNum, endSegmentNum) {
this._validateSegment(startSegmentNum, endSegmentNum);
const { isSegmentUsed, usedSegmentList } = this.isSegmentUsed(
startSegmentNum,
endSegmentNum,
);
if (isSegmentUsed) {
usedSegmentList.forEach(([startSegmentNum, endSegmentNum]) => {
this._updateSegmentList(startSegmentNum, endSegmentNum, null);
this._usedSegmentMap.delete(
JSON.stringify([startSegmentNum, endSegmentNum]),
);
});
}
return usedSegmentList;
}
/**
* 获取全部可用的区间段
* @returns {Array<[number, number]>}
*/
getFreeSegment() {
let tempStartSegmentNum = -1;
const freeSegmentList = [];
for (let i = 0; i < this._segmentList.length; i++) {
const segment = this._segmentList[i];
if (segment === null) {
if (i + 1 === this._segmentList.length) {
freeSegmentList.push([tempStartSegmentNum, i]);
} else if (tempStartSegmentNum < 0) {
tempStartSegmentNum = i;
}
} else {
if (tempStartSegmentNum >= 0) {
freeSegmentList.push([tempStartSegmentNum, i - 1]);
tempStartSegmentNum = -1;
}
}
}
return freeSegmentList;
}
/**
* 获取全部已用的区间段
* @returns {Array<[number, number]>}
*/
getUsedSegmentList() {
const set = new Set();
this._segmentList.forEach((segment) => {
if (segment !== null) {
set.add(JSON.stringify(segment));
}
});
const segmentStrList = Array.from(set);
return segmentStrList.map((segmentStr) => JSON.parse(segmentStr));
}
}
export default SegmentListUtilBase;映射胶水层
javascript
// DayTimePickValidate.js
import SegmentListUtilBase from "./SegmentListUtilBase";
class DayTimePickValidate {
/** 用于保存{@link SegmentListUtilBase}实例 */
_segmentListUtil = undefined;
/** 时间块步长为30分钟，通过调整这个步长来调整一块时间块表示的时间长度 */
_step = 30;
constructor(step) {
this._step = step ?? this._step;
/**
* 一天 1440 分钟，用 1440 除以 {@link _step}， 计算出一共需要多少个时间块
*/
this._segmentListUtil = new SegmentListUtilBase(1440 / this._step);
}
/**
* 将形如 "00:12"、"23:59"、"24:00"的时间格式，转换成基于分钟步长的区间下标
* @example
* 假设基于总分钟数为1440分钟（1天的总分钟数），步长为 30 分钟，则有：
* - 00:00 => 0
* - 00:01 => 0
* - 00:29 => 0
* - 00:30 => 1
* - 00:31 => 1
* - 01:00 => 2
* - 01:30 => 3
* - 以此类推……
* 假设基于总分钟数位1440分钟（1天的总分钟数），步长为 20 分钟，则有：
* - 00:00 => 0
* - 00:01 => 0
* - 00:29 => 1
* - 00:30 => 1
* - 00:31 => 1
* - 00:40 => 2
* - 01:00 => 3
* - 01:20 => 4
* - 01:30 => 4
* - 以此类推……
* @param {string} timeText 需要转换的时间文本
* @param {number} step 基础步长，影响到时间前面的小时的部份的逻辑
* @returns {number} 转换后的下标
*/
_timeToSegment(timeText, step = this._step) {
/** 校验传入的时间格式是否正确，该正则的逻辑参考当前目录下的图片 ./TimeReg.png */
const timeReg = /^(((([0-1]?\d)|(2[0-3])):([0-5]?\d))|(24:00))$/g;
if (!timeReg.test(timeText)) {
throw new Error("传入的时间格式不正确，其范围范围为 00:00 - 24:00");
} else {
const [hoursStr, minutesStr] = timeText.split(":");
const hours = Number.parseInt(hoursStr);
const minutes = Number.parseInt(minutesStr);
return Math.floor(hours * (60 / step)) + Math.floor(minutes / step);
}
}
/**
* 胶水方法，将时间块的编号转换成格式为"mm:ss"的时间字符串
* @private
* @param {number} index 时间块编号
* @returns {string} 格式为"mm:ss"的时间字符串
*/
_segmentToTime(index) {
const totalMinutes = index * this._step;
const hours = Math.floor(totalMinutes / 60);
const minutes = totalMinutes % 60;
const hoursStr = `00${hours}`.slice(-2);
const minutesStr = `00${minutes}`.slice(-2);
return `${hoursStr}:${minutesStr}`;
}
/**
* 胶水方法，将时间块区间数组转换成时间字符串数组
* @private
* @example
* const result = _segmentListToTimeArrangeList([[0, 1], [2, 2]])
* // 则 result 的值为
* [['00:00', '01:00'], ['01:00', '01:30']]
* @param {Array<[number, number]>} segmentList 时间块区间数组
* @returns {Array<[string, string]>} 基于格式为"mm:ss"的时间字符串，拼接成的时间字符串数组
*/
_segmentListToTimeArrangeList(segmentList) {
return segmentList.map(([startIndex, endIndex]) => {
return [
this._segmentToTime(startIndex),
this._segmentToTime(endIndex + 1),
];
});
}
/**
* 胶水方法，校验给定的时间字符串是否合法：起始时间必须小于结束时间
* @private
* @param {string} startTimeStr 起始时间
* @param {string} endTimeStr 结束时间
* @throws {Error} 起始时间必须小于结束时间
*/
_validateTimeArrange(startTimeStr, endTimeStr) {
const startIndex = this._timeToSegment(startTimeStr);
const endIndex = this._timeToSegment(endTimeStr);
if (startIndex >= endIndex) {
throw new Error("起始时间必须小于结束时间");
}
}
/**
* @typedef {Object} AddTimeArrangeResult
* @property {boolean} isSuccess 是否标识成功
* @property {Array<[string, string]>} [usedTimeList] 被使用的区间列表
* @property {string} [message] 错误信息（如果有）
*/
/**
* 将给定的时间范围标识为已使用，如果该时间范围未被占用，则{@link isSuccess}会返回成功;否则{@link isSuccess}会返回失败以及已被占用的时间范围{@link usedTimeList}
* @param {string} startTimeStr 格式为"mm:ss"的起始时间字符串
* @param {string} endTimeStr 格式为"mm:ss"的结束时间字符串
* @returns {AddTimeArrangeResult}
*/
addTimeArrange(startTimeStr, endTimeStr) {
try {
this._validateTimeArrange(startTimeStr, endTimeStr);
} catch (error) {
return {
isSuccess: false,
message: error.message,
};
}
const startIndex = this._timeToSegment(startTimeStr);
const endIndex = this._timeToSegment(endTimeStr);
const {
isSuccess,
usedSegmentList,
} = this._segmentListUtil.addSegment(startIndex, endIndex - 1);
let usedTimeList = [];
if (!isSuccess) {
usedTimeList = this._segmentListToTimeArrangeList(usedSegmentList);
}
return {
isSuccess,
usedTimeList,
};
}
/**
* 清除传入的时间标识段段占用标识
* @param {string} startTimeStr 格式为"mm:ss"的起始时间字符串
* @param {string} endTimeStr 格式为"mm:ss"的结束时间字符串
* @returns {Array<[string, string]>} 被传入的时间段覆盖而清除的时间段
*/
removeTimeArrange(startTimeStr, endTimeStr) {
this._validateTimeArrange(startTimeStr, endTimeStr);
const startIndex = this._timeToSegment(startTimeStr);
const endIndex = this._timeToSegment(endTimeStr);
const removeSegmentList = this._segmentListUtil.removeSegment(
startIndex,
endIndex - 1,
);
return this._segmentListToTimeArrangeList(removeSegmentList);
}
/**
* 给定的时间段字符串是否被占用
* @param {string} startTimeStr 格式为"mm:ss"的起始时间字符串
* @param {string} endTimeStr 格式为"mm:ss"的结束时间字符串
* @returns {boolean} true 表示被占用， false 表示未占用
*/
isTimeArrangeUsed(startTimeStr, endTimeStr) {
const startIndex = this._timeToSegment(startTimeStr);
const endIndex = this._timeToSegment(endTimeStr);
const { isSegmentUsed, usedSegmentList } =
this._segmentListUtil.isSegmentUsed(startIndex, endIndex);
return isSegmentUsed;
}
/**
* 获取当前实例下，已占用的时间段
* @returns {Array<[string, string]>} 已占用的时间段
*/
getUsedSegmentList() {
const list = this._segmentListUtil.getUsedSegmentList();
return this._segmentListToTimeArrangeList(list);
}
}
export default DayTimePickValidate;使用DayTimePickValidate类实现业务需求
js
// 默认分段步长为 30 分钟，所以一天分成 48 段
const dayTimePickValidate = new DayTimePickValidate()
// 添加时间段 '00:00' - '12:00'
const {
isSuccess, // 是否插入成功的布尔值
usedTimeList, // 如果插入失败，是因为哪些时间段被占用导致的失败
message // 如果有其他异常，会通过该字段返回
} = dayTimePickValidate.addTimeArrange('00:00', '12:00')
// 这个方法会把前面添加的['00:00', '12:00']移除，因为['00:00', '00:30'] 在['00:00', '12:00']的范围内
dayTimePickValidate.removeTimeArrange('00:00', '00:30')
// 添加时间段 '00:00' - '00:30'
const {
isSuccess, // 是否插入成功的布尔值
usedTimeList, // 如果插入失败，是因为哪些时间段被占用导致的失败
message // 如果有其他异常，会通过该字段返回
} = dayTimePickValidate.addTimeArrange('00:00', '00:30')
let isTimeArrangeUsed = dayTimePickValidate.isTimeArrangeUsed('00:00', '01:00') // true
isTimeArrangeUsed = dayTimePickValidate.isTimeArrangeUsed('00:00', '00:30') // true
isTimeArrangeUsed = dayTimePickValidate.isTimeArrangeUsed('01:00', '01:30') // false
// 添加时间段 '12:00' - '12:30'
const {
isSuccess, // 是否插入成功的布尔值
usedTimeList, // 如果插入失败，是因为哪些时间段被占用导致的失败
message // 如果有其他异常，会通过该字段返回
} = dayTimePickValidate.addTimeArrange('12:00', '12:30')
const usedSegmentList = dayTimePickValidate.getUsedSegmentList() // [['00:00', '00:30'], ['12:00', '12:30']]