## SQL Challenge Response: Finding Consecutive Available Blocks in a Schedule

(Note: Updated 5/15/2007 @ 12:25 PM EST to show another possible solution with different results.)

Here's my response to the SQL Challenge given here. The challenge involves having a schedule table with days and times, and displaying all available consecutive free time slots to schedule an event.

This can be tough to solve in SQL, but it can be done. One way is using the "run/streak detection" technique shown here (my very first SQLTeam article from quite a few years back), and another is basically using my favorite join - a CROSS JOIN! Both solutions are given below.

Note that I changed his schema a little; the table has a natural primary key of Day/TimeSlot, and TimeSlot is just an integer so that I could create simple sample data with only 8 "TimeSlots" per day.

(

[day] datetime not null,

TimeSlot int not null,

Booked bit not null,

primary key ([day],TimeSlot)

)

-- add some sample data

insert into schedule

select '1/1/2007',1,0 union all

select '1/1/2007',2,0 union all

select '1/1/2007',3,0 union all

select '1/1/2007',4,1 union all

select '1/1/2007',5,0 union all

select '1/1/2007',6,1 union all

select '1/1/2007',7,0 union all

select '1/1/2007',8,0 union all

select '1/2/2007',1,0 union all

select '1/2/2007',2,0 union all

select '1/2/2007',3,0 union all

select '1/2/2007',4,0 union all

select '1/2/2007',5,1 union all

select '1/2/2007',6,0 union all

select '1/2/2007',7,0 union all

select '1/2/2007',8,0 union all

select '1/3/2007',1,0 union all

select '1/3/2007',2,1 union all

select '1/3/2007',3,1 union all

select '1/3/2007',4,0 union all

select '1/3/2007',5,0 union all

select '1/3/2007',6,0 union all

select '1/3/2007',7,1 union all

select '1/3/2007',8,0

With our sample data in place, here's one fairly simple solution (only 1 SQL statement) using the run/streak method that returns available time ranges that will accommodate blocks the size of the @TimeSlotsNeeded variable:

set @timeSlotsNeeded = 3

select [day], min(TimeSlot) as StartTime, max(TimeSlot) as EndTime

from

(select s.[day], s.TimeSlot, s.Booked,

(select count(*) from schedule s2

where s2.[day] = s.[day] and

s2.TimeSlot <= s.TimeSlot and

s2.Booked != s.Booked

) as RunGroup

from schedule s

) x

where

x.Booked = 0

group by

[day], RunGroup

having count(*) >= @TimeSlotsNeeded

----------------------- ----------- -----------

2007-01-01 00:00:00.000 1 3

2007-01-02 00:00:00.000 1 4

2007-01-02 00:00:00.000 6 8

2007-01-03 00:00:00.000 4 6

(4 row(s) affected)

Note that, as mentioned in the comments, this solution will return basically only 1 row for the entire day if the entire day is open. If you really want to return all possible blocks of time that are open, then see the next solution.

Solution #2

Here, we use basically a CROSS JOIN (in this case, actually an INNER JOIN that has a cross-join effect) to join the schedule table to itself, joining each time slot per day to the next @TimeSlotsNeeded after it that are open. If the join results in @TimeSlotsNeeded matches, we have that entire block open. We can determine this by GROUPing on TimeSlot and ensuring that the COUNT(*) equals the @TimeSlotsNeeded, as shown:

set @timeSlotsNeeded = 3

select s.Day, s.TimeSlot, max(s2.TimeSlot) as EndTime

from schedule s

inner join schedule s2

on s2.day =s.day and

s2.TimeSlot between s.TimeSlot and s.TimeSlot + @TimeSlotsNeeded- 1

where

s.Booked = 0 and s2.Booked = 0

group by s.Day, s.TimeSlot

having count(*) = @TimeSlotsNeeded

----------------------- ----------- -----------

2007-01-01 00:00:00.000 1 3

2007-01-02 00:00:00.000 1 3

2007-01-02 00:00:00.000 2 4

2007-01-02 00:00:00.000 6 8

2007-01-03 00:00:00.000 4 6

(5 row(s) affected)

# Legacy Comments

codist
2007-05-15 |
re: SQL Challenge Response: Finding Consecutive Available Blocks in a Schedule Does this deal correctly with data where there are 4 open slots in a row, where you need to get 0-1-2 and 1-2-3. Your sample data doesn't have such a run (and I don't have sqlserver so I'll have to mess with the sql to find out). |

Jeff
2007-05-15 |
re: SQL Challenge Response: Finding Consecutive Available Blocks in a Schedule Right now, it will just return 0-3 meaning that you can pick any 3 consecutive timeslots within that range, which I feel is a good, clear answer that should meet the needs. I don't believe the specification indicated how to return such results. For example, if I need to schedule an hour of time, typically I would only need to know that I can schedule any hour between 12:00 and 5:00, not that I can schedule 12-1 or 12:30-1:30 or 1-2 or 1:30-2:30, etc ... |

Jeff
2007-05-15 |
re: SQL Challenge Response: Finding Consecutive Available Blocks in a Schedule Article has been updated to show two solutions, the second returns the data that you are looking for. |

codist
2007-05-15 |
re: SQL Challenge Response: Finding Consecutive Available Blocks in a Schedule Whohoo, #2 works! I knew it was some kind of cross-join but never quite got the idea right. |

Deepak
2007-06-11 |
re: SQL Challenge Response: Finding Consecutive Available Blocks in a Schedule Select t1.ID as slot1,SUM(CASE WHEN t2.ID = (t1.ID + 1) THEN 1 ELSE 0 END) as status from test t1 inner join test t2 on t1.Number = t2.Number WHERE t1.Number = 1 AND t2.Number = 1 GROUP BY t1.ID ORDER BY t1.ID table test is as follows : The number 1 indicates a blank slot...ID is the time slot ID. Eight half hour time slots and we need to find whether there are any two consecutive half hour slots....basically i have chosen 2 as the number but it can be parametrized.. ID Number ----------- ----------- 1 1 2 1 3 2 4 1 5 1 6 1 7 3 8 1 |

Bob
2009-09-20 |
re: SQL Challenge Response: Finding Consecutive Available Blocks in a Schedule Hello, I have a similar challenge, which is inspired by the one presented here. Here it is: I have a table t1 with columns like this: ID int, value int. ID value ----------- ----------- 1 1 2 1 3 2 4 5 5 5 6 5 7 3 8 1 9 0 10 11 11 24 12 17 13 2 14 1 15 1 16 23 17 15 18 17 19 0 20 1 The challenge is to present a result set which is based on several parameters. Show the startingID and the EndingID of all consecutive records with value greater than 10 and with more than 2 consecutive occurrences. Also, show the first value of the set, the last value, and the min and max value of the current consecutive occurrence group. The above query based on the data in t1 would return the following: StartingID EndingID StartingValue EndingValue MinValue MaxValue 10 12 11 17 11 24 16 18 23 17 15 23 I hope this challenge can be solved in sql server 2005/2008. |