Search code examples
sqlmysqlintervals

Find the next datetime determined by overlaping intervals

I can have at maximum N intervals running in the same period. An interval starts at time X and ends at time X + 7 (one week).

Is there any way to get the next date where I can start a new interval such that I don't exceed N? For example:

N=3

1       8
|-------|
 2       9
 |-------|
  3       10
  |-------|

        8
        |--- can start here

A table example:

CREATE TABLE intervals (
    num int,
    valid_from datetime,
    valid_until datetime
);
INSERT INTO intervals 
  (num, valid_from, valid_until)
VALUES
  (1, NOW(), ADDDATE(NOW(), 7)),
  (2, ADDDATE(NOW(), 1), ADDDATE(NOW(), 8)),
  (3, ADDDATE(NOW(), 2), ADDDATE(NOW(), 9));

I tried some approaches using window functions, but I am not sure how to make them run over time intervals instead of rows. Maybe this is not the best approach, but I am wondering if this is possible to do in SQL only.

Solution

  • Consider case when we do not any assumption about intervals (regularity,duration and so on).

    1. Collect all events - start and stop process (interval).
    2. Count running intervals for every event time - qty.
    3. Calculate max count running intervals for every row - from this row to last, ordered by event date - maxnext.
    4. Find first (one) row, where running intervals qty<N and further running intervals all <N.

    See example.
    Test data

    num valid_from valid_until
    1 2024-07-19 23:58:45 2024-07-26 23:58:45
    2 2024-07-20 23:58:45 2024-07-27 23:58:45
    3 2024-07-21 23:58:45 2024-07-28 23:58:45
    4 2024-07-22 23:58:45 2024-07-29 23:58:45

    Output before filter and limit

    num dt running qty maxnext
    1 2024-07-19 23:58:45 1 1 4
    2 2024-07-20 23:58:45 1 2 4
    3 2024-07-21 23:58:45 1 3 4
    4 2024-07-22 23:58:45 1 4 4
    1 2024-07-26 23:58:45 -1 3 3
    2 2024-07-27 23:58:45 -1 2 2
    3 2024-07-28 23:58:45 -1 1 1
    4 2024-07-29 23:58:45 -1 0 0

    Result

    num dt qty maxnext
    2 2024-07-27 23:58:45 2 2 
    with t as(
  select *
    ,max(qty)over(order by dt rows between current row and unbounded following)maxnext
  from(
    select num,dt,running,sum(running)over(order by dt)qty
    from(
      select num,valid_from dt, 1 running
      from intervals
      union all
      select num,valid_until, -1 running
      from intervals
    )allevents
  )running_qty
)
select  *
from t
where qty<3 and maxnext<3
order by dt 
limit 1

    demo

    Update1. For case when your data have gaps, as shown in comment and fiddle (dbfiddle.uk/Hvs8LdKG):

    When we want find time slots, available to run next service process, we can find time intervals, where running process count < N.

    with allevents as(
 select num,dt,running,sum(running)over(order by dt)qty
    ,row_number()over(order by dt) rn
 from(
    select num,valid_from dt, 1 running
    from intervals
    union all
    select num,valid_until, -1 running
    from intervals
  )x
)
,t as(
  select *
    ,sum(newgr)over(order by dt)grn
  from(
    select num,dt,running,qty,rn
      ,case when qty>=3 and lag(qty,1,0)over(order by dt)<=2
              or qty<=2 and lag(qty,1,0)over(order by dt)>=3
        then 1 else 0 end newgr
    from allevents
 )running_qty
)
,grint as(
  select grn,min(rn)n1,max(rn)n2
    ,min(dt)fromdt,max(dt) todt
    ,min(qty)qtymin,max(qty) qtymax
    ,lead(min(dt))over(order by grn) nextgrdt
    ,case when adddate(min(dt),7)<lead(min(dt))over(order by grn)
          or lead(min(dt))over(order by grn) is null
        then 1 else 0 end slot
--  ,timediff(nextEvent,dt) td
  from t
  group by grn
)
-- select * from grint order by grn;

select fromdt,nextgrdt todo -- *
from grint
where slot=1 
order by grn
-- limit 1

    Let's reduce task to a dumb task like "gaps and islands". Group consecutive rows where the number of running processes is more than 3 and less than 3.

    num dt running qty rn newgr grn
    1 2024-07-23 09:21:17 1 1 1 0 0
    2 2024-07-24 09:21:17 1 2 2 0 0
    3 2024-07-25 09:21:17 1 3 3 1 1
    4 2024-07-26 09:21:17 1 4 4 0 1
    1 2024-07-30 09:21:17 -1 3 5 0 1
    2 2024-07-31 09:21:17 -1 2 6 1 2
    3 2024-08-01 09:21:17 -1 1 7 0 2
    4 2024-08-02 09:21:17 -1 0 8 0 2
    5 2024-08-12 09:21:17 1 3 9 1 3
    6 2024-08-12 09:21:17 1 3 10 0 3
    7 2024-08-12 09:21:17 1 3 11 0 3
    5 2024-08-19 09:21:17 -1 0 12 1 4
    6 2024-08-19 09:21:17 -1 0 13 0 4
    7 2024-08-19 09:21:17 -1 0 14 0 4

    Grouped intervals

    grn n1 n2 fromdt todt qtymin qtymax nextgrdt slot
    0 1 2 2024-07-23 09:21:17 2024-07-24 09:21:17 1 2 2024-07-25 09:21:17 0
    1 3 5 2024-07-25 09:21:17 2024-07-30 09:21:17 3 4 2024-07-31 09:21:17 0
    2 6 8 2024-07-31 09:21:17 2024-08-02 09:21:17 0 2 2024-08-12 09:21:17 1
    3 9 11 2024-08-12 09:21:17 2024-08-12 09:21:17 3 3 2024-08-19 09:21:17 0
    4 12 14 2024-08-19 09:21:17 2024-08-19 09:21:17 0 0 null 1

    Then, take all or one available time slots

    fromdt todt(nextgrdt)
    2024-07-31 09:21:17 2024-08-12 09:21:17
    2024-08-19 09:21:17 null

    Demo