Checking for time range overlap, the watchman problem [SQL]

Question

I am running into a road block on a larger problem.

As part of a large query I need to solve a "night watchman" problem. I have a table with schedule shifts as such:

ID | Start          | End
1  | 2009-1-1 06:00 | 2009-1-1 14:00
2  | 2009-1-1 10:00 | 2009-1-1 18:00
3  | 2009-2-1 20:00 | 2009-2-2 04:00
4  | 2009-2-2 06:00 | 2009-2-2 14:00

As part of a query, I need to determine if there is at least 1 watchman in a room at all times for a given time range.

So if I specified the range 2009-1-1 06:00 to 2009-1-1 12:00, the result is true, because shifts 1 and 2 merge to cover this time period - in fact any number of shifts could be chained to keep the watch up. However if I checked 2009-2-1 22:00 to 2009-1-2 10:00, the result is false because there is a break between 4 and 6am the following morning.

I would like to implement this either in LINQ, or as a user defined function in SQL Server (2005), as in both cases this is just a part of the logic of a larger query that must be run to identify elements that need attention. The real dataset involves about a hundred shift records intersecting any given time period, but not always covering the whole range.

The closest I've found is How to group ranged values using SQL Server for number ranges, however it depends on each range ending just before the next range starts. If I could construct the same unified view of the watches, only taking overlapping watches into consideration, then it would be trivial to check if a specific time was covered. A unified view would look like this:

Start          | End
2009-1-1 06:00 | 2009-1-1 18:00
2009-2-1 20:00 | 2009-2-2 04:00
2009-2-2 06:00 | 2009-2-2 14:00

Note: This whole thing would be relatively easy to implement by just pulling all the data and running some manual loop on it, however that is the current system, and its rather slow because of the number of shifts and the number of time ranges that must be checked.

Answer 1

Here is a way to flatten date range like this

Start          | End
2009-1-1 06:00 | 2009-1-1 18:00
2009-2-1 20:00 | 2009-2-2 04:00
2009-2-2 06:00 | 2009-2-2 14:00

You have to compare previous and next dates in each row and see whether

• Current row's Start date falls between previous row's date range.
• Current row's End date falls between next row's date range.

Using above code, implementing UDF is as simple as followed.

create function fnThereIsWatchmenBetween(@from datetime, @to datetime)
returns bit
as
begin
    declare @_Result bit

    declare @FlattenedDateRange table (
        Start   datetime,
        [End]   datetime
    )

    insert  @FlattenedDateRange(Start, [End])
    select  distinct 
            Start = 
                case 
                    when Pv.Start is null then Curr.Start 
                    when Curr.Start between Pv.Start and Pv.[End] then Pv.Start
                    else Curr.Start 
                end,
            [End] = 
                case 
                    when Curr.[End] between Nx.Start and Nx.[End] then Nx.[End] 
                    else Curr.[End] 
                end
    from    shift Curr
            left join shift Pv on Pv.ID = Curr.ID - 1 --; prev
            left join shift Nx on Nx.ID = Curr.ID + 1 --; next

    if exists(  select  1
                from    FlattenedDateRange R
                where   @from between R.Start and R.[End]
                        and @to between R.Start and R.[End]) begin
        set @_Result = 1    --; There is/are watchman/men during specified date range
    end
    else begin
        set @_Result = 0    --; There is NO watchman
    end

    return @_Result
end

Answer 2

An unguarded interval obviously starts either at the end of a watched period or at the beginning of the whole time range that you are checking. So you need a query that selects all elements from this set that don't have an overlapping shift. The query would look like:

select 1 
from shifts s1 where not exists
    (select 1 from shifts s2
     where s2.start<=s1.end and s2.end > s1.end
    )
    and s1.end>=start_of_range and s1.end<  end_of_range
union
select 1 
where not exists
    (select 1 from shifts s2 
      where s2.start<=start_of_range and s2.end > start_of_range
    )

If this is non-empty, then you have an unguarded interval. I suspect it will run in quadratic time, so it might be slower than "sort, fetch and loop".