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

Date: Sat, 04 Dec 2004 10:34:44 +0100

Message-ID: <31deqjF391ln6U1_at_individual.net>

Mikito Harakiri wrote:

> 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.
*

Easy with OLAP functions:

CREATE TABLE Intervals

(

x INT NOT NULL, y INT NOT NULL, CHECK (x <= y), PRIMARY KEY (x,y)

);

INSERT INTO Intervals VALUES (1,3); INSERT INTO Intervals VALUES (2,5); INSERT INTO Intervals VALUES (4,11); INSERT INTO Intervals VALUES (10,12);

INSERT INTO Intervals VALUES (20,21);

INSERT INTO Intervals VALUES (120,130); INSERT INTO Intervals VALUES (120,128); INSERT INTO Intervals VALUES (120,122); INSERT INTO Intervals VALUES (121,132); INSERT INTO Intervals VALUES (121,122); INSERT INTO Intervals VALUES (121,124); INSERT INTO Intervals VALUES (121,123); INSERT INTO Intervals VALUES (126,127);

SELECT min_x, MAX(y)

**FROM
**

(

** SELECT
**

x,y, MAX(CASE WHEN x <= max_y THEN NULL ELSE x END) OVER (ORDER BY x, y ROWS UNBOUNDED PRECEDING) AS min_x

**FROM**

(

SELECT x, y, MAX(y) OVER(ORDER BY x, y ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING ) AS max_y FROM intervals

) dt

) dt

GROUP BY min_x

**ORDER BY 1;**

- Query completed. 3 rows found. 2 columns returned.
- Total elapsed time was 1 second.

min_x Maximum(y)

----------- -----------

1 12 20 21 120 132

Dieter Received on Sat Dec 04 2004 - 10:34:44 CET