Re: SQL competition: the shortest interval coalesce/pack query

From: Lennart Jonsson <>
Date: 3 Dec 2004 12:28:02 -0800
Message-ID: <>

"Mikito Harakiri" <> wrote in message news:<2uPrd.61$>...
> Write the shortest sql query that would return a minimal cover of a set of
> intervals. For example, given
> Intervals = {(x=1,y=3), (x=2,y=5), (x=4, y=11), (x=10,y=12), (x=20,y=21)}
> it should return
> cover(Intervals) = {(x=1,y=12), (x=20,y=21)}
> "Developing Time-Oriented..." book by R.Snordgrass demonstrates several
> rather lenthy solutions (pp.160+). The book is freely downloadable.
> To be able to compare results, lets agree that each of the clauses (select,
> from, where, group by, having) starts a new line. (Each subquery/inner view
> must obey this rule as well.) Also, no more than 2 column expressions are
> allowed to fit on a single line in the select clause. Likewise, no more than
> 2 view/tables are allowed on a single line within from clause, no more than
> 2 predicates in the each line of the where clause, etc. If anybody knows
> alternative (maybe even standard) sql formatting rules, you are welcome to
> suggest those.

I have not looked at the article, so I'm not sure this is any shorter but:

with cover(x,y,n) as (

    select x, y, 1 from intervals
    union all
    select c.x, i.y, n+1 from cover c, intervals i     where c.y > i.x
      and (n+1) < (select count(1) from intervals) )
select x, max(y) from cover c

where not exists (

    select 1 from cover where y=c.y and x < c.x ) group by x

tested with
create table intervals (

        x int not null,
        y int not null,
        primary key (x,y)


insert into intervals (x,y) values (1,3),(2,5),(4,11),(10,12),(20,21);

/Lennart Received on Fri Dec 03 2004 - 21:28:02 CET

Original text of this message