Compute total job duration of calendar events with possible overlaps

Vladimir Moldovanenko 26 Reputation points
2021-05-26T20:10:31.727+00:00

Hi.

Thanks for looking at my challenge.

The challenge is to compute total duration of service jobs for a work center given individual job start/finish times. Jobs may overlap.

DECLARE @CalendarEvents TABLE  
(  
    wrcID int NOT NULL -- work center  
    ,jobID int NOT NULL -- job to perform  
    -- calendar  
    ,ceStartDateTime datetimeoffset(0) NOT NULL  
    ,ceFinishDateTime datetimeoffset(0) NOT NULL  
    ,PRIMARY KEY(wrcID, jobID)  
)  
INSERT INTO @CalendarEvents  
VALUES  
(1, 1, '2021-05-26 08:00:00.0000000 -05:00', '2021-05-26 08:30:00.0000000 -05:00')  
,(1, 2, '2021-05-26 08:30:00.0000000 -05:00', '2021-05-26 09:00:00.0000000 -05:00')  
,(1, 3, '2021-05-26 09:10:00.0000000 -05:00', '2021-05-26 09:40:00.0000000 -05:00')  
,(1, 4, '2021-05-26 09:10:00.0000000 -05:00', '2021-05-26 09:40:00.0000000 -05:00')  
,(1, 5, '2021-05-26 09:10:00.0000000 -05:00', '2021-05-26 09:30:00.0000000 -05:00')  
,(1, 6, '2021-05-26 09:20:00.0000000 -05:00', '2021-05-26 09:30:00.0000000 -05:00')  
,(1, 7, '2021-05-26 09:50:00.0000000 -05:00', '2021-05-26 10:00:00.0000000 -05:00')  
  
,(2, 10, '2021-05-26 08:00:00.0000000 -05:00', '2021-05-26 08:30:00.0000000 -05:00')  
,(2, 11, '2021-05-26 08:20:00.0000000 -05:00', '2021-05-26 08:50:00.0000000 -05:00')  
  
  
SELECT ce.*  
    ,DATEDIFF(minute, ce.ceStartDateTime, ce.ceFinishDateTime) SegmentDuration_Mins  
FROM @CalendarEvents ce  
  
-- Compute the total job duration by work center, considering any overlaps, expected result  
SELECT *  
FROM(VALUES (1, 100), (2, 50)) v(wrcID, TotalDuration_Mins)  
  
-- wrong result  
SELECT  
    ce.wrcID  
    ,SUM(DATEDIFF(minute, ce.ceStartDateTime, ce.ceFinishDateTime)) TotalDuration_Mins  
FROM @CalendarEvents ce  
GROUP BY  
    ce.wrcID  

This can be represented as follows

100004-2021-05-26-14-53-01-calendar.jpg

the right result is: 120 - 20 = 100 minutes in duration for all scheduled jobs. It's apparent that straight aggregation will not account for overlaps.

If you have any idea(s), even if this is in an approach, please let me know.

Thanks for your time and expertise. I appreciate it.

Vladimir

Transact-SQL
Transact-SQL
A Microsoft extension to the ANSI SQL language that includes procedural programming, local variables, and various support functions.
4,515 questions
0 comments No comments
{count} vote

Accepted answer
  1. Viorel 109.8K Reputation points
    2021-05-27T09:00:30.847+00:00

    Check an alternative approach too:

    ;
    with G as
    (
        select *,
            concat('POLYGON ((', s, ' 0,', s, ' 1, ', e, ' 1, ', e, ' 0, ', s, ' 0))') as p 
        from @CalendarEvents
        cross apply (select min(ceStartDateTime) from @CalendarEvents) M(m)
        cross apply (values (datediff(minute, m, ceStartDateTime), datediff(minute, m, ceFinishDateTime))) D(s, e)
    )
    select wrcID, geometry::UnionAggregate(p).STArea() as TotalDuration_Mins
    from G
    group by wrcID
    
    1 person found this answer helpful.
    0 comments No comments

6 additional answers

Sort by: Most helpful
  1. MelissaMa-MSFT 24,176 Reputation points
    2021-05-27T03:19:32.637+00:00

    Hi @Vladimir Moldovanenko ,

    Welcome to Microsoft Q&A!

    Please refer below and check whether it is working.

    ;With cte AS (  
    SELECT wrcID, ceStartDateTime, ceFinishDateTime  
        , LastStop = MAX(ceFinishDateTime)   
                    OVER (PARTITION BY wrcID ORDER BY ceStartDateTime, ceFinishDateTime ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING)  
    FROM   @CalendarEvents  
    ), cte1 AS (  
    SELECT wrcID, ceStartDateTime, ceFinishDateTime  
        , Block = SUM(CASE WHEN LastStop Is Null Then 1  
                            WHEN LastStop < ceStartDateTime Then 1 ELSE 0 END)  
                    OVER (PARTITION BY wrcID ORDER BY ceStartDateTime, LastStop)  
    FROM   cte  
    ),cte2 as (  
    SELECT wrcID  
        , MIN(ceStartDateTime) ceStartDateTime  
        , MAX(ceFinishDateTime) ceFinishDateTime  
    FROM   cte1  
    GROUP BY wrcID, Block)  
    SELECT wrcID,SUM(DATEDIFF(minute, ceStartDateTime, ceFinishDateTime))  TotalDuration_Mins  
    FROM cte2  
    GROUP BY  wrcID  
    

    Output:

    wrcID TotalDuration_Mins  
    1 100  
    2 50  
    

    Above query could be working with SQL Server 2012 and later.

    If above is not working, please provide more sample data and expected output.

    Best regards,
    Melissa


    If the answer is helpful, please click "Accept Answer" and upvote it.
    Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.

    1 person found this answer helpful.
    0 comments No comments

  2. Vladimir Moldovanenko 251 Reputation points
    2021-05-27T16:26:03.377+00:00

    Melissa, Viorel,
    Thanks a lot for your ideas!

    I have reviewed in your solutions in details and understood them well.

    Melissa, your solution queries table once only, which is of value for me. I really liked how you determined and marked blocks, which is just elegant. I'll add this method to my mental toolbox.

    Viorel, your solution is incredibly unique in approach and elegance. It's brilliant!
    I've used geometry to calculate complex panel part area and perimeter length, however using it to plot time would have never occur to me!
    There is missing correlation on wrcID in line: (select min(ce_m.ceStartDateTime) from @CalendarEvents ce_m WHERE ce_m.wrcID = ce.wrcID) M(m). I would consider this a minor typo.

    From plan 'Estimated Subtree Cost' point of view Viorel's solution is the 'cheapest' too.

    Viorel-1: 0.0079287
    Vladimir: 0.0193457
    Melissa: 0.0375818

    Therefore, I would consider Viorel's solution a winner.

    Thank you. I have learned a lot.

    1 person found this answer helpful.

  3. Vladimir Moldovanenko 251 Reputation points
    2021-05-27T03:28:37.76+00:00

    Melissa, Thanks a lot.
    I will review your suggestion in details in the morning.

    I came up with a solution myself so I am curious to compare.

    SELECT SUM(DATEDIFF(minute, ov.StartMin, ov.FinishMax)) TotalDuration_Mins
    FROM
    (
        SELECT DISTINCT
            ce.wrcID
            ,ov.OverlapingJobs
            ,ov.StartMin
            ,ov.FinishMax
        FROM @CalendarEvents ce
        CROSS APPLY
        (
            SELECT
                STRING_AGG(ov.jobID, ',') WITHIN GROUP(ORDER BY ov.jobID) as OverlapingJobs
                ,MIN(ov.ceStartDateTime) StartMin
                ,MAX(ov.ceFinishDateTime) FinishMax
            FROM @CalendarEvents ov
            WHERE ov.wrcID = ce.wrcID
            --AND ov.jobID != ce.jobID
            -- range overlap. Two ranges overlap if (StartA <= EndB) and (EndA >= StartB)
            AND ce.ceStartDateTime <= ov.ceFinishDateTime
            AND ce.ceFinishDateTime >= ov.ceStartDateTime
        ) ov
    ) ov
    GROUP BY
        ov.wrcID
    
    0 comments No comments

  4. Erland Sommarskog 98,636 Reputation points
    2021-05-27T21:15:54.58+00:00

    Here is one more take on it. I don't think this is the most efficient, since it is fairly simpleminded. It is based on using a table of numbers. It works as long as you want results on minute level, but it would not be equally practical, if you wanted results on second level. (Or more precisely, how big precision you want in regards to the time intervals.)

    ; WITH minmax AS (
       SELECT MIN(ceStartDateTime) AS mintime, MAX(ceFinishDateTime) AS maxtime
       FROM   @CalendarEvents
    )
    SELECT COUNT(*)
    FROM   Numbers n
    JOIN   minmax mm ON n.n BETWEEN 1 AND DATEDIFF (MINUTE, mm.mintime, mm.maxtime) + 1
    WHERE  EXISTS(SELECT *
                  FROM   @CalendarEvents CE
                  WHERE  CE.ceStartDateTime  <= dateadd(MINUTE, n.n-1, mm.mintime)
                    AND  CE.ceFinishDateTime > dateadd(MINUTE, n.n-1, mm.mintime))
    

    If you are unfamiliar with tables of numbers, I have a short story here:
    https://www.sommarskog.se/Short%20Stories/table-of-numbers.html.

    0 comments No comments