3

Sirs,

I have a ticketing system. Now I have to select adjacent places when the user asks for 2 or 3 tickets. Every ticket has a line and column number. The concept of adjacent places is places in the same line with adjacent columns numbers. These tickets are in a sql server database. Any ideas about this algorithm to search for available adjacent seats?

Regards,

Camilo

1
  • Sounds like a fun problem. Got a sample table? Offhand, I'm thinking of a join against a table that has fully fleshed-out version of the seat-space. (i.e. join a partially-sold bus/train/plane against a fully sold one, show seating rows that meat your minimum # of seats criteria, and then filter for seat adjacency.) Commented Dec 28, 2009 at 21:29

3 Answers 3

5

You can get two adjacent seats by joining the table aginst itself on Column = Column+1:

SELECT ...
FROM Seats A
JOIN Seats B ON A.Row = B.Row AND A.Column = B.Column+1
WHERE A.IsReserved = 0
AND B.IsReserved = 0

You can extend this to 3-4 seat chains by joining repeatedly on Column=Column+1, +2, +3. If you want a more generic solution for any sequence length you're going to have to use recursive CTEs and it gets complicated. For most use cases the simple join will work fine.

For example:

create table Seats (Row int not null
  , Col int not null
  , IsReserved bit not null
  , constraint pkSeatsRowColumn primary key (Row, Col));
go
insert into Seats (Row, Col, IsReserved)
select 1,1,0 union all
select 1,2,0 union all
select 1,3,1 union all
select 1,4,0 union all
select 1,5,0 union all
select 1,6,0 union all
select 2,1,0;

with cteAnchor as (
  SELECT Row, Col, 1 as [length]
  FROM Seats
  WHERE IsReserved = 0)
, cteRecursive as (
  SELECT Row, Col, [length]
  FROM cteAnchor
  UNION ALL
  SELECT c.Row, c.Col, c.[length]+1
  FROM Seats s
  JOIN cteRecursive c
    ON s.Row = c.Row and s.Col = c.Col+c.[length]
  WHERE s.IsReserved = 0)
select * from cteRecursive 

The recursive query will return all available seat sequences in a set that contains the starting seat number and the length of the sequnce. If you want only sequences of length 3, you add the necessary WHERE clause and the query will return the seat (1,4) that is the only one with 2 more available seats next to it in my sample data.

1
CREATE TABLE #Places(LineNumber INT, ColumnNumber INT, IsOccupied CHAR(1));
GO

DECLARE @NumAdjacent INT;

SET @NumAdjacent = 3;

SELECT * FROM #Places AS p
WHERE @NumAdjacent = (SELECT COUNT(*) FROM #Places AS p1
 WHERE p1.LineNumber = p.LineNumber
 AND p1.ColumnNumber BETWEEN p.ColumnNumber AND p.ColumnNumber + @NumAdjacent - 1
 AND p1.IsOccupied = 'Y');
2
  • 1
    This is going to return all end row seats, because the NOT EXISTS condiftion will be satisfied by 'inexsiting' seats. Commented Dec 28, 2009 at 21:47
  • You could use a COUNT instead in the subquery. If the number of existing free seats between col and col+@num is exactly @num, it's a match. Commented Dec 28, 2009 at 21:50
0
WITH    places AS
        (
        SELECT   1 AS row, 1 AS col, 0 AS occupied
        UNION ALL
        SELECT   1 AS row, 2 AS col, 1 AS occupied
        UNION ALL
        SELECT   1 AS row, 3 AS col, 0 AS occupied
        UNION ALL
        SELECT   1 AS row, 4 AS col, 0 AS occupied
        UNION ALL
        SELECT   1 AS row, 5 AS col, 0 AS occupied
        UNION ALL
        SELECT   1 AS row, 6 AS col, 1 AS occupied
        )
SELECT  row, col, len
FROM    (
        SELECT  row, col, COUNT(*) OVER (PARTITION BY row, span) AS len
        FROM    (        
                SELECT  row, col,
                        col - ROW_NUMBER() OVER (PARTITION BY row ORDER BY col) AS span
                FROM    places
                WHERE   occupied = 0
                ) q
        ) q2
WHERE   len >= 3

This query returns all free spans of 3 places or more.

The basic idea here is that the columns are contiguous though all seats and the ROW_NUMBER's are contiguous only within the free seats:

column  occupied  ROW_NUMBER  diff
1       0         1           0
2       1         -           -
3       0         2           1
4       0         3           1
5       0         4           1
6       1         -           -

The spans of free seats have the same difference between the column and the ROW_NUMBER and this difference can be used to group them.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.