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

From: Dieter Nöth <dnoeth_at_gmx.de>
Date: Sat, 04 Dec 2004 10:34:44 +0100
Message-ID: <31deqjF391ln6U1@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 - 03:34:44 CST