时间冲突

本文结束时间冲突的算法。

起源

做个两个类似的项目，第一个是会议，第二个是广告。相同需求，已占用的时间段，不可用，即判断时间冲突。在做广告项目的时候，有了新想法，单独记录一下。

算法

以下假设开始时间是12、结束时间14号。假设数据库的数据都是合法的，即开始时间<=结束时间。选择的时间段，也是合法的时间，也是开始<=结束。

选择时间段12~14，即12、13、14这三天被占用。包含边界。

先讲述最差的算法，再慢慢迭代算法。

大概穷举出以下情况：

情况	12之前	12~14之间	14之后	冲突
1	开始结束
2	开始	结束		√
3	开始		结束	√
4		开始结束		√
5		开始	结束	√
6			开始结束

从上表可是看出，判断不冲突的条件最为简单，即结束>12或者开始<14，那么肯定不冲突，除此以外，都冲突。（但是怎么转化为独立面）

判断冲突，情况3最容易忽略。

会议预约中使用的算法

是否时间冲突，核心是判断数据库内是否有1条记录，与1214的时间段有重叠。所以呢，查出的数据，1、要么开始在1214号之间，2、要么结束在12~14号之间，3、要么，开始>12且结束>14（针对表格情况3）。

所以上面三种条件的关系是： 条件1 or 条件2 or 条件3。

优化版本一

可以这么考虑，要么 一调记录的开始 在12~14之间，要么12在开始、结束之间。简单理解，要么我（时间段一）的开始在你（时间段二）之间，要么你的开始在我之间。

所以，上面两种的条件，：条件1 or 条件2

上面的版本是同事，想出来的，我顿时觉得很不错，算法好多了。

优化版本二

其实最开始想的是，判断时间冲突不好判断，但是判断时间不冲突好判断（从对立面考虑）。即如下：

开始  > 14  或   结束 < 12

但是上面要取反才行。所以在查询的时候，大概要这么写

select * from meeting where not (start> 14 or end < 12)

但是，对于逻辑的运算，我可能有点差，不敢优化上面的代码，后来，我试了一下逻辑合并，

not ( start > 14   or end < 12 )
好像等价于
not (start > 14)  and   not (end < 12 )
好像就是
start <=14  and end >= 12

这样判断冲突就简化为下面的sql

select id from meeting where start<=14 and end>=12 limit 1;

即，只要能查出来一个id，则表示存在冲突的会议。这样一下精简了非常多。当然，上面的前提是开始<=结束时间 。但是好处是：1、精简了判断，2、or变成了and 效率提高了。

然后尝试画了一个图，好像确实能行。