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

"John Gilson" <jag_at_acm.org> wrote in message news:1103442412.157933.6240_at_f14g2000cwb.googlegroups.com...
> 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
>

Sorry about the formatting folks. A "benefit" of the new Google Groups. Let's try again.

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

--
JAG