如何比较高效的判断n个时间段中，不能存在交集或者子集？

Question

有n个时间段 如下图所示：

其中每个时间段不能与其他时间段交叉（如 时间段1：10:00:00-12:00:00,时间段2：10:30:00-13:00:00），或者不能被包含（如 时间段1：10:00:00-12:00:00,时间段2：07:30:00-20:00:00）

时间段的个数没有限制，前后顺序没有限制。怎么处理比较高效呢？

现在通过sort 排序之后，比较下个时间段的开始时间 是否大于 当前时间段的结束时间来处理。是否有更好的办法解决呢？

Answer 1

你本身的办法是有问题的，只比较一次会有漏洞，我有个想法，你可以试试效率：
将每一组时间转化为时间戳，生成 key=时间戳 value = 数组号
统一按照key 排序，检测相邻组号，不连续 或者 新数组结果数量小于理论值（时间戳有完全重复，key覆盖 )）

Answer 2

排序后再比较这种操作的最后效率取决于你排序的效率了，一般都是O(nlogn)，如果还想再快，那只能想O(n)复杂度的方法了。
方法1：O(n),需要看你的业务情况
假如时间都是半个小时一截的，一天24小时，可以分成48个半个小时，那么可以用长度为48的数组表示这半个小时是否被占用，0未占用 1占用，例如a = [1,1,0,...] 就表示00:00 ~ 00:30、00:30 ~ 01:00是占用的。如果你是一个内存吝啬型的人，那么可以考虑用位运算来表示时间占用情况。
这样以来，遍历到每一个元素直接查数组看是不是被占用了就行，时间复杂度是O(n)

方法2：最坏O(nlogn)，二分 + 插入排序，比直接排序稍微好点
维持一个以开始时间有序的、无时间冲突的数组，判断一个时间段a是否与现有安排冲突，先拿a的开始时间用二分法找插入位置，找到后与前后元素比较看是否冲突，不冲突的话就插入。这个算法最坏情况是每次都没有冲突，这样会导致每次都要把元素后挪，所以最坏情况下是O(nlogn)，如果安排经常冲突的话，这个算法是不错的。

暂时只想到这2个

Answer 3

有相关的代码嘛