Cropping overlapping timespans by priority in SQL server

Question

I have a large database table with timespans described by start and stop time. Easy timespan has a priority and the timespans might overlap each other.

I need to process it so that overlaps will be removed.
In case of an overlap, the span with a higher priority will take precedence and the timespan with lower priority will be cropped so that the two doesn't overlap. If a time span is completely overlapped by one or more timespans with higher priority, it should be removed.

A simple example table:

SELECT
    1 AS id,
    {ts '2012-09-24 10:00:00'} AS start,
    {ts '2012-09-24 11:00:00'} AS stop,
    10 AS priority
INTO #TABLE
UNION ALL SELECT 2, {ts '2012-09-24 10:15:00'}, {ts '2012-09-24 12:00:00'}, 5
UNION ALL SELECT 3, {ts '2012-09-24 10:30:00'}, {ts '2012-09-24 12:30:00'}, 1
UNION ALL SELECT 4, {ts '2012-09-24 11:30:00'}, {ts '2012-09-24 13:00:00'}, 15

SELECT * FROM #TABLE;
DROP TABLE #TABLE;

Should result in:

Start              Stop               Priority
2012-09-24 10:00   2012-09-24 11:00   10
2012-09-24 11:00   2012-09-24 11:30   5
2012-09-24 11:30   2012-09-24 13:00   15

It is possible, but I can't find any simple solution to it. Preferably I would like to avoid using cursors. But if there is no other way, well, cursors it is.

Answer 1

Try

;with cte as 
(select start as timepoint from @table union select stop from @table)
,cte2 as (select *, ROW_NUMBER() over (order by timepoint) rn from cte) 

    select id, MIN(ts) as starttime, max(te) as stoptime, maxpri
    from @table t2
        inner join
        (               
        select ts, te, MAX(priority) as maxpri 
        from @table t1
            inner join
            (       
            select c1.rn, c1.timepoint as ts, c2.timepoint as te 
            from cte2 c1
            inner join cte2 c2 on c1.rn+1 = c2.rn
            ) v
            on t1.start<v.te and t1.stop>v.ts
        group by ts, te
        ) v
            on t2.priority = v.maxpri
            and ts>=start and te<=stop
        group by id, maxpri
        order by starttime