SQL Challenge Response: Finding Consecutive Available Blocks in a Schedule

Tue May 15, 2007 by Jeff Smith in t-sql, techniques, efficiency, links, datetime-data

(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.

create table schedule
(
    [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

Solution #1

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:

declare @timeslotsNeeded int
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

day                     StartTime   EndTime

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

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:

declare @timeslotsNeeded int
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

Day                     TimeSlot    EndTime
----------------------- ----------- -----------
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.