Quote: |

This is the case where you are Ticketek, and you get a group of 4 people who want to book seats together. You must find all the places in the theatre where there are 4 or more vacant seats all next to each other. For our purposes, assume that we have n people, so we need n or more vacant seats in a row. Ignore the problem that in most theatres the seat numbers aren't adjacent at the ends of rows. (Assume that we have a circular amphitheatre with the seats in a continuous spiral.) Return a row with the starting number for each set of n adjacent seats. It would be even better if you could return a single row for each block of of available seats of n or more, so if n=4, and 101-106 are available, then the row (101,6) would be preferable to 101,102,103. The input will be as follows. If there are 1000 seats in the theatre, then there will be 1000 rows in the table, with an indicator for whether each seat is booked or not. |

Here's a script to create the table and fill it with random but deterministic data.

DROP TABLE seats / CREATE TABLE seats ( seat INTEGER PRIMARY KEY, booked INTEGER CHECK (booked IN (0,1)) ) / DECLARE -- Each PI decimal gives the number of adajacent seats -- with the same booked/unbooked status s_pi CONSTANT VARCHAR2(510) := '3' || '14159265358979323846264338327950288419716939937510' || '58209749445923078164062862089986280348253421170679' || '82148086513282306647093844609550582231725359408128' || '48111745028410270193852110555964462294895493038196' || '44288109756659334461284756482337867831652712019091' || '45648566923460348610454326648213393607260249141273' || '72458700660631558817488152092096282925409171536436' || '78925903600113305305488204665213841469519415116094' || '33057270365759591953092186117381932611793105118548' || '07446237996274956735188575272489122793818301194912'; i_pi PLS_INTEGER := 1; -- PI decimal i_seat PLS_INTEGER := 0; -- seat number i_booked PLS_INTEGER := 1; -- 1=booked, 0=unbooked i_nb PLS_INTEGER; -- number of seats with same status BEGIN LOOP EXIT WHEN i_seat >= 1000; i_nb := TO_NUMBER(SUBSTR(s_pi,i_pi,1)) + 1; FOR j in 1..i_nb LOOP EXIT WHEN i_seat+j > 1000; INSERT INTO seats VALUES (i_seat+j, i_booked); END LOOP; i_seat := i_seat + i_nb; i_pi := i_pi + 1; i_booked := 1 - i_booked; END LOOP; COMMIT; END; /

Enjoy!

Regards

Michel

]]>

SQL> select seat, booked, 2 case 3 when nvl(lag(booked) over (order by seat),1-booked) != booked 4 then seat 5 end flag 6 from seats 7 order by seat 8 / SEAT BOOKED FLAG ---------- ---------- ---------- 1 1 1 2 1 3 1 4 1 5 0 5 6 0 7 1 7 8 1 9 1 10 1 11 1 12 0 12 13 0 14 1 14 15 1 16 1 17 1 18 1 19 1 20 0 20 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 29 rows selected.

At second step, I repeat/propagate this flag to all subsequent seats with the same status:

SQL> with 2 step1 as ( 3 select seat, booked, 4 case 5 when nvl(lag(booked) over (order by seat),1-booked) != booked 6 then seat 7 end flag 8 from seats 9 ) 10 select seat, booked, max (flag) over (order by seat) grp 11 from step1 12 order by seat 13 / SEAT BOOKED GRP ---------- ---------- ---------- 1 1 1 2 1 1 3 1 1 4 1 1 5 0 5 6 0 5 7 1 7 8 1 7 9 1 7 10 1 7 11 1 7 12 0 12 13 0 12 14 1 14 15 1 14 16 1 14 17 1 14 18 1 14 19 1 14 20 0 20 21 0 20 22 0 20 23 0 20 24 0 20 25 0 20 26 0 20 27 0 20 28 0 20 29 0 20 29 rows selected.

Now, "flag" (which has been renamed to "grp") gives me each successive groups with same status.

Group 1 is booked, group 5 is free, group 7 is booked, group 12 is free, group 14 is booked and group 20 is free.

The next step is to get the minimal and maximal seat numbers and the number of seats in each group, limiting to the groups that are unbooked:

SQL> with 2 step1 as ( 3 select seat, booked, 4 case 5 when nvl(lag(booked) over (order by seat),1-booked) != booked 6 then seat 7 end flag 8 from seats 9 ), 10 step2 as ( 11 select seat, booked, max (flag) over (order by seat) grp 12 from step1 13 ) 14 select min(seat) first_seat, max(seat) last_seat, count(*) nb_seat 15 from step2 16 where booked = 0 17 group by grp 18 order by 1 19 / FIRST_SEAT LAST_SEAT NB_SEAT ---------- ---------- ---------- 5 6 2 12 13 2 20 29 10 3 rows selected.

Now, we just have to search for the rows/groups that satisfy the condition: a number of successive unbooked seats greater or equal the resqueted number.

With the full table, this gives:

SQL> def nb=6 SQL> with 2 step1 as ( 3 select seat, booked, 4 case 5 when nvl(lag(booked) over (order by seat),1-booked) != booked 6 then seat 7 end flag 8 from seats 9 ), 10 step2 as ( 11 select seat, booked, max (flag) over (order by seat) grp 12 from step1 13 ), 14 step3 as ( 15 select min(seat) first_seat, max(seat) last_seat, count(*) nb_seat 16 from step2 17 where booked = 0 18 group by grp 19 ) 20 select first_seat||'-'||last_seat seats 21 from step3 22 where nb_seat >= &nb 23 order by first_seat 24 / SEATS --------------------------------------------------------------------------------- 20-29 33-39 56-64 75-82 164-171 182-187 201-209 227-234 237-243 268-277 282-289 299-304 318-327 361-366 393-401 404-410 436-442 456-465 476-484 19 rows selected. SQL> def nb=9 SQL> / SEATS -------------------- 20-29 56-64 201-209 268-277 318-327 393-401 456-465 476-484 8 rows selected.

Regards

Michel

]]>

Regards

Michel

]]>

SELECT Seat - Amount + 1 Seat, Amount FROM ( SELECT Seat, MAX(Level) Amount FROM Seats WHERE CONNECT_BY_ISLEAF = 1 START WITH Booked = 0 CONNECT BY Seat = PRIOR Seat + 1 AND Booked = 0 GROUP BY Seat ) WHERE Amount >= 4 ORDER BY Seat;

Could you explain it, the purpose of these SQL puzzles is to help to learn SQL tricks and features.

Regards

Michel

]]>

The base query is creating a set of seats where they are all empty, and we'll throw in Level to find the offset:

SELECT Seat, Level Amount FROM Seats START WITH Booked = 0 CONNECT BY Seat = PRIOR Seat + 1 AND Booked = 0

The START BY applies the CONNECT BY restricted of unbooked seats to the first seat as well.

The problem is, this allows each member in the set to start its own string. That is, if 2 is a child of 1, it'll be in there twice, once with an offset of 0 (when it is the parent) and once with an offset of 1 (when it is a child of 1).

The solution is two-fold.

1) Find the last member in the set. That's CONNECT_BY_ISLEAF = 1.

2) Being there are many sets, as each member starts its own set, use GROUP BY and MAX(Level) to get the leaf with the highest offset.

SELECT Seat, MAX(Level) Amount FROM Seats WHERE CONNECT_BY_ISLEAF = 1 START WITH Booked = 0 CONNECT BY Seat = PRIOR Seat + 1 AND Booked = 0 GROUP BY Seat;

So, now we have the sets we want, and how many seats in each set. The problem now is, the seat listed is the final member in the set. That is easily solved, just subtract the amount of members from the final member and add one.

SELECT Seat - MAX(Level) + 1, MAX(Level) Amount FROM Seats WHERE CONNECT_BY_ISLEAF = 1 START WITH Booked = 0 CONNECT BY Seat = PRIOR Seat + 1 AND Booked = 0 GROUP BY Seat;

Perfect. That lists all sets of seats more than 1 in a row.

Now we can add the simple requirement of the puizzle. That it be 4 or more.

SELECT Seat - MAX(Level) + 1, MAX(Level) Amount FROM Seats WHERE CONNECT_BY_ISLEAF = 1 AND Level >= 4 START WITH Booked = 0 CONNECT BY Seat = PRIOR Seat + 1 AND Booked = 0 GROUP BY Seat;

Michel

]]>

Note on the previous query: the final step (main query) should easily be merged into the previous one (named step3), I separated these steps to explain the query and let you now merge them. [/img]

Very nicely summarized Michel. As you said, step3 could be resolved into single step using LISTAGG(11g onwards) :

SQL> WITH step1 2 AS (SELECT seat, 3 booked, 4 CASE 5 WHEN Nvl(Lag(booked) 6 over ( 7 ORDER BY seat), 1 - booked) != booked THEN seat 8 END flag 9 FROM seats), 10 step2 11 AS (SELECT seat, 12 booked, 13 Max (flag) 14 over ( 15 ORDER BY seat) grp 16 FROM step1 17 WHERE booked = 0 18 ORDER BY seat) 19 SELECT * 20 FROM (SELECT Listagg(seat, ',') 21 within GROUP(ORDER BY grp) seat_range, 22 Count(*) cnt 23 FROM step2 24 GROUP BY grp) 25 WHERE cnt > 4; SEAT_RANGE CNT -------------------------------------------------------------------------------- ---------- 20,21,22,23,24,25,26,27,28,29 10 33,34,35,36,37,38,39 7 56,57,58,59,60,61,62,63,64 9 75,76,77,78,79,80,81,82 8 113,114,115,116,117 5 135,136,137,138,139 5 164,165,166,167,168,169,170,171 8 182,183,184,185,186,187 6 201,202,203,204,205,206,207,208,209 9 227,228,229,230,231,232,233,234 8 237,238,239,240,241,242,243 7 268,269,270,271,272,273,274,275,276,277 10 282,283,284,285,286,287,288,289 8 299,300,301,302,303,304 6 318,319,320,321,322,323,324,325,326,327 10 336,337,338,339,340 5 351,352,353,354,355 5 361,362,363,364,365,366 6 393,394,395,396,397,398,399,400,401 9 404,405,406,407,408,409,410 7 SEAT_RANGE CNT -------------------------------------------------------------------------------- ---------- 436,437,438,439,440,441,442 7 456,457,458,459,460,461,462,463,464,465 10 476,477,478,479,480,481,482,483,484 9 509,510,511,512,513 5 564,565,566,567,568,569,570,571 8 582,583,584,585,586,587,588,589,590 9 601,602,603,604,605,606,607,608,609 9 611,612,613,614,615,616,617,618,619 9 627,628,629,630,631,632 6 642,643,644,645,646,647,648,649,650 9 659,660,661,662,663,664,665 7 673,674,675,676,677 5 710,711,712,713,714 5 720,721,722,723,724,725,726 7 728,729,730,731,732,733,734,735,736,737 10 744,745,746,747,748,749 6 751,752,753,754,755,756 6 778,779,780,781,782,783,784,785 8 789,790,791,792,793,794 6 799,800,801,802,803,804 6 815,816,817,818,819 5 SEAT_RANGE CNT -------------------------------------------------------------------------------- ---------- 821,822,823,824,825,826,827,828,829 9 844,845,846,847,848 5 872,873,874,875,876 5 887,888,889,890,891,892,893,894,895 9 918,919,920,921,922,923,924,925,926,927 10 932,933,934,935,936,937,938,939,940 9 955,956,957,958,959,960 6 967,968,969,970,971,972 6 983,984,985,986,987,988,989 7 995,996,997,998,999 5 51 rows selected

Looking for more such puzzles!

Thanks to you and Ross ]]>