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

From: Tony <andrewst_at_onetel.com>
Date: 3 Dec 2004 07:21:42 -0800

"Mikito Harakiri" <mikharakiri_at_iahu.com> wrote in message news:<2uPrd.61\$G45.36_at_news.oracle.com>...
> 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
>
> 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.

Are we allowed to use analytic functions? I believe they are part of the SQL standard these days, though I only know the Oracle dialect:

SELECT starts.x, ends.y
FROM (SELECT x, ROW_NUMBER() OVER(ORDER BY x) rn

```        FROM   (SELECT x, y,
LAG(y) OVER(ORDER BY x) prev_y
FROM   intervals)
WHERE  prev_y is null
OR     prev_y < x ) starts,
(SELECT y, ROW_NUMBER() OVER(ORDER BY y) rn
FROM   (SELECT x, y,