Jeff's SQL Server Blog

Random Thoughts & Cartesian Products with Microsoft SQL Server
posts - 157, comments - 2686, trackbacks - 64

My Links

Advertisement

News

Welcome to my weblog. My name is Jeff Smith, I am software developer in Boston, MA and I was recently named a 2009 SQL Server MVP. Check in frequently for tips, tricks, commentary and ideas on SQL Server and .NET programming.


Subscribe





Archives

Post Categories

Programming

Sports

SQL

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.

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)

Print | posted on Tuesday, May 15, 2007 9:52 AM | Filed Under [ T-SQL Techniques Efficiency Links DateTime Data ]

Feedback

Gravatar

# 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).
5/15/2007 11:16 AM | codist
Gravatar

# 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 ...
5/15/2007 11:41 AM | Jeff
Gravatar

# 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.
5/15/2007 12:25 PM | Jeff
Gravatar

# 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.
5/15/2007 2:50 PM | codist
Gravatar

# 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
6/11/2007 11:41 AM | Deepak
Gravatar

# 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.
9/20/2009 2:51 AM | Bob
Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET