603. Consecutive Available Seats


Several friends at a cinema ticket office would like to reserve consecutive available seats.
Can you help to query all the consecutive available seats order by the seat_id using the following cinema table? 
| seat_id | free |
|---------|------|
| 1       | 1    |
| 2       | 0    |
| 3       | 1    |
| 4       | 1    |
| 5       | 1    |

Your query should return the following result for the sample case above.

| seat_id |
|---------|
| 3       |
| 4       |
| 5       |
Note:
  • The seat_id is an auto increment int, and free is bool ('1' means free, and '0' means occupied.).
  • Consecutive available seats are more than 2(inclusive) seats consecutively available.


    • b'
    \n
    \n\n
    \n

    Solution

    \n
    \n

    Approach: Using self join and abs()[Accepted]

    \n

    Intuition

    \n

    There is only one table in this problem, so we probably need to use self join for this relative complex problem.

    \n

    Algorithm

    \n

    First, let\'s see what we have after joining this table with itself.

    \n
    \n

    Note: The result of join two tables is the Cartesian product of these two tables.

    \n
    \n
    select a.seat_id, a.free, b.seat_id, b.free\nfrom cinema a join cinema b;\n
    \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    seat_idfreeseat_idfree
    1111
    2011
    3111
    4111
    5111
    1120
    2020
    3120
    4120
    5120
    1131
    2031
    3131
    4131
    5131
    1141
    2041
    3141
    4141
    5141
    1151
    2051
    3151
    4151
    5151
    \n

    To find the consecutive available seats, the value in the a.seat_id should be more(or less) than the value b.seat_id, and both of them should be free.

    \n
    select a.seat_id, a.free, b.seat_id, b.free\nfrom cinema a join cinema b\n  on abs(a.seat_id - b.seat_id) = 1\n  and a.free = true and b.free = true;\n
    \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    seat_idfreeseat_idfree
    4131
    3141
    5141
    4151
    \n

    At last, choose the concerned column seat_id, and display the result ordered by seat_id.

    \n
    \n

    Note: You may notice that the seat with seat_id \'4\' appears twice in this table. This is because seat \'4\' next to \'3\' and also next to \'5\'. So we need to use distinct to filter the duplicated records.

    \n
    \n

    MySQL

    \n
    select distinct a.seat_id\nfrom cinema a join cinema b\n  on abs(a.seat_id - b.seat_id) = 1\n  and a.free = true and b.free = true\norder by a.seat_id\n;\n
    \n
    '