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

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.

CREATE TABLE Intervals
(
x INT NOT NULL,
y INT NOT NULL,
CHECK (y > x),
PRIMARY KEY (x,y)
);

INSERT INTO Intervals (x, y)
VALUES (1,3),(2,5),(4,11),(10,12),(20,21); SELECT MIN(I.x) AS cover_x, cover_y
FROM (SELECT I.x AS x, MIN(Y.y) as cover_y FROM (SELECT I1.y AS y
FROM Intervals AS I1
WHERE NOT EXISTS (SELECT *
FROM Intervals AS I2
WHERE I2.y > I1.y AND
I2.x <= I1.y)) AS Y
INNER JOIN
Intervals AS I
ON I.y <= Y.y
GROUP BY I.x) AS I
GROUP BY cover_y;

cover_x cover_y

1	12
20	21

--
JAG