确定最大重叠时间范围的数量

Question

我得到了一个包含一些 DATETIME 范围的表，类似于：

id | start               | end
----------------------------------------------
1  | 2011-12-18 16:00:00 | 2011-12-18 17:00:00
2  | 2011-12-19 08:00:00 | 2011-12-19 10:00:00
3  | 2011-12-19 11:00:00 | 2011-12-19 13:00:00
4  | 2011-12-19 12:00:00 | 2011-12-19 14:00:00
5  | 2011-12-19 13:00:00 | 2011-12-19 15:00:00
6  | 2011-12-19 13:00:00 | 2011-12-19 14:00:00
7  | 2011-12-20 13:00:00 | 2011-12-20 14:00:00

因此，对于2011年12月19日，范围如下：

8    9   10   11   12   13   14   15
<-------->
               <-------->
                    <-------->
                         <-------->
                         <---->

当插入新的记录时，目标是找到已经存在的最大重叠范围数量：例如：当插入新的范围2011-12-19 12:00:00 - 2011-12-19 15:00:00时，我希望收到3，因为最大重叠范围的数量是3，从13:00到14:00。

现在我已经实现了这个功能。

select
    count(*) as cnt
from
    mytable as p
where
    ( # check if new renge overlap existings ones
        (@start >= start and @start < end)
        or
        (@end > start and @end <= end)
    )
    or
    ( # check if existing range is included by new one
        start between @start and @end
        and
        end between @start and @end
    )

但是这会返回4，因为它检测除第一个外的所有范围，但是这是错误的。

我已经找到了以下内容：

• 确定两个日期范围是否重叠
• 如何在SQL中选择重叠的日期范围
• 检查时间重叠的表格？

但是所有这些问题都略有不同。

我使用的是MySQL 5.7，但如果必要，升级到8是可能的。

- fudo

---

@CetinBasoz 为什么示例数据和期望输出不匹配？ - fudo

@RadimBača 如问题末尾所述，我目前使用的是MySQL 5.7，但如果必要的话升级到8也不是什么大问题。 - fudo

好的，你期望的输出仍然不匹配。请检查我给出的查询语句，它返回正确的输出，应该是4（有4个重叠的范围，而不是3个）。 - Cetin Basoz

@CetinBasoz，我还不明白我有哪4个范围重叠，请您指出开始/结束时间？ - fudo

所有id为3、4、5、6的行与给定范围重叠。 - Cetin Basoz

Answer 1

这篇答案适用于包含窗口函数的MySQL 8.0版本。解决方案的核心将是以下查询，该查询针对数据中每个有趣的区间查找一定数量的重叠区间：

select t2.startDt, t2.endDt, count(*) overlaps_count
from
(
    select lag(t1.dt) over (order by t1.dt) startDt, t1.dt endDt
    from
    (
        select startt dt from data
        union
        select endt dt from data
    ) t1
) t2
join data on t2.startDt < data.endt and t2.endDt > data.startt
group by t2.startDt, t2.endDt

DBFiddle DEMO

有了这个结果（我们称之为Overlap table），您就可以轻松地找到输入区间的最大值，方法如下：

with Overlap as
(
   -- the query above
)
select max(overlaps_count)
from Overlap 
where @start < endDt and @end > startDt

- Radim Bača

---

是的，这个工作正常，但是你说的另一个超级查询，不如在原始查询中添加一个where子句来过滤落在新查询范围内的范围，这样不是更好吗？ - fudo

甚至更好的是，在最内部的“union”选择中添加“where”子句？ - fudo

@fudo 我不确定第一个区间，因为它将包含 null 而不是 DateTime。我认为即使在我的解决方案中，第一个区间也需要一些 null 处理，然后您可以将条件放入最嵌套的子查询中。最好的。 - Radim Bača

您的意思是在使用 lag() 函数的 select 语句中吗？是的，这条记录的 startDT 字段将为 null，但 endDT 将与传入范围的起始时间重合，因此我认为它会被丢弃（作为信息），因为它与我感兴趣的范围无关。 - fudo

@fudo没错！在这种情况下，您可以将“@start < endDt and @end > startDt”条件移入“Overlap”查询。 - Radim Bača

我刚刚注意到你在主查询中的select和group by语句中都引用了表别名t1，你应该使用别名t2进行更正；之前我没有注意到这个问题，因为我重新排列了你的查询以适应我的特定用例。 - fudo

Answer 2

考虑起始点和结束点不会相同：

select
    count(*) as cnt
from
    mytable as p
where
    # check if new renge overlap existings ones
        (@start < end and @end > start);

- Cetin Basoz

---

我认为这也会返回4吧？因为它不会得到最大重叠范围，而是所有重叠的范围，对吗？ - ChatterOne

@ChatterOne，"最大重叠范围"是什么意思？它与重叠范围的数量有何不同？ - Cetin Basoz

看一下这个例子，你会发现重叠的范围是 [11-13, 12-14] 和 [12-14, 13-15, 13-14]。使用你的查询，你将得到 4 作为结果，因为如果任何一个范围与任何其他范围重叠，那么就会计数。但是如果你想知道最大数量的范围彼此重叠，那就是不同的查询。在这种情况下，数字是 3，因为存在 [12-14, 13-15, 13-14] 的值。 - ChatterOne

@ChatterOne，抱歉我不明白你的意思。这里有4个重叠的范围。 - Cetin Basoz

是的，有4个范围，但它们并不全部相互重叠。范围11-13仅与12-14重叠。例如，它不会与13-15重叠。总共有两个范围彼此重叠，另外三个范围也相互重叠。 - ChatterOne

@ChatterOne，显然我错过了你的评论。那里有4个重叠的范围。13-15也是一个重叠的范围。它与12-14和13-14重叠。 - Cetin Basoz