Wednesday, January 21, 2009

A Basic Code for Seat Reservation Algorithm

I receive this question from the forum that I frequently visit. Given a list of availabe seat number, I need to return the first available free seats based on the required number seats.

Say the following are the available seats:
1, 2, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Say you need 1 seat, the first available seat is 1.
Say you need 2 seats, the first available seats are 1-2.
Say you need 3 seats, the first available seats are 5, 6, 7
Say you need 4 seats, the first available seats are 5, 6, 7, 8
Say you need 5 seats, the first available seats are 10, 11, 12, 13, 14

Although there are a number of ways to return the available seats, I believe some the processing has to be done on the front-end than just leaving everything on the back-end. Here is my recommended query:
declare @seat table (seatnum smallint)
declare @NumberOfSeatsNeeded smallint

insert into @seat (seatnum) values(1);
insert into @seat (seatnum) values( 2);
insert into @seat (seatnum) values( 5);
insert into @seat (seatnum) values( 6);
insert into @seat (seatnum) values( 7);
insert into @seat (seatnum) values( 8);
insert into @seat (seatnum) values( 10);
insert into @seat (seatnum) values( 11);
insert into @seat (seatnum) values( 12);
insert into @seat (seatnum) values( 13);
insert into @seat (seatnum) values( 14);
insert into @seat (seatnum) values( 15);
insert into @seat (seatnum) values( 16);
insert into @seat (seatnum) values( 17);
insert into @seat (seatnum) values( 18);
insert into @seat (seatnum) values( 19);
insert into @seat (seatnum) values( 20)

set @NumberOfSeatsNeeded = 3

select startseat, endseat,
(endseat - startseat) + 1 as numberofseats
from
(select
startseat =
(select top 1 a.seatnum
  from @seat a
left join @seat b on a.seatnum = b.seatnum + 1
where
   b.seatnum + 1 is null and x1.seatnum > a.seatnum
 order by 1 desc), 
x1.seatnum as endseat
from
(select x.seatnum
from @seat x
left join @seat y on x.seatnum = y.seatnum + 1
where y.seatnum + 1 is not null) x1
union all
select a.seatnum as startseat, b.seatnum as endseat
from @seat a
inner join @seat b on a.seatnum = b.seatnum) vacantseats
where(endseat - startseat) + 1 = @NumberOfSeatsNeeded
order by 1, 3
As I mentioned, there are other ways of doing this. Improvements are always welcome...

~~ CK

No comments:

Post a Comment