TSQL Exhaust Available Slots

Question

I have a set of users that register when they're available for particular meetings (slots). I have them mapped to each other and need to fill in the first available slot they can both meet, without double-booking them.

I have included an example of how I got to where I am solving it, but I'm stuck on how to get further.

CREATE TABLE #Slot (slot int, start datetime)
INSERT INTO #Slot VALUES (11, DATEADD(hour, 1, '1/1/1900 7:00:00'))
INSERT INTO #Slot VALUES (22, DATEADD(hour, 2, '1/1/1900 7:00:00'))
INSERT INTO #Slot VALUES (31, DATEADD(hour, 3, '1/1/1900 7:00:00'))
INSERT INTO #Slot VALUES (44, DATEADD(hour, 4, '1/1/1900 7:00:00'))
INSERT INTO #Slot VALUES (56, DATEADD(hour, 5, '1/1/1900 7:00:00'))
INSERT INTO #Slot VALUES (61, DATEADD(hour, 6, '1/1/1900 7:00:00'))
INSERT INTO #Slot VALUES (77, DATEADD(hour, 7, '1/1/1900 7:00:00'))
INSERT INTO #Slot VALUES (83, DATEADD(hour, 8, '1/1/1900 7:00:00'))

CREATE TABLE #Av (reg int, slot int)
INSERT INTO #Av
SELECT 1, slot
FROM #Slot
INSERT INTO #Av
SELECT 2, slot
FROM #Slot
INSERT INTO #Av
SELECT 3, slot
FROM #Slot
INSERT INTO #Av
SELECT 4, slot
FROM #Slot


CREATE TABLE #Met (reg1 int, reg2 int, slot int)
INSERT INTO #Met (reg1, reg2) VALUES (1, 2)
INSERT INTO #Met (reg1, reg2) VALUES (1, 3)
INSERT INTO #Met (reg1, reg2) VALUES (4, 2)

What I End up with using the following CTE is all times they can meet, but I don't know how to only end up with three rows. What I expect to end up with (using the data provided) is this:

reg1  reg2  slot
1     2     11
1     3     22 --since 1 is meeting with 2 already in slot 11
4     2     22 --since 2 is meeting with 1 already in slot 11

Here's what I have so far...basically all options, but cannot get down to the three rows:

with poss(opt, r1, r2, slot) AS
(
SELECT
    ROW_NUMBER() OVER(PARTITION BY m.reg1, m.reg2 ORDER BY s1.start),
    m.reg1, m.reg2, s1.slot
FROM #Met m
INNER JOIN #Av r1 ON m.reg1 = r1.reg
INNER JOIN #Slot s1 ON r1.slot = s1.slot
INNER JOIN #Av r2 ON m.reg2 = r2.reg
INNER JOIN #Slot s2 ON r2.slot = s2.slot
WHERE r1.slot = r2.slot
)

SELECT
    *
FROM poss e
INNER JOIN #met m ON e.r1 = m.reg1 AND e.r2 = m.reg2
ORDER BY opt

It would help if you used clearer names and valid Ids in your examples. I guess #av is the available table, listing registrants' availability to slots? #met is meetings, and your example is showing meeting requests between registrants: 1+2, 1+3, 4+2? The expected output shows slot 1, but that doesn't exist, presumably you mean 11? Should #met.slot be updated with the assigned slot? — gregmac, Dec 12 '11 at 23:29
Is the code you're looking for is supposed to do bulk scheduling for several meetings at once, without overlapping any meetings? Is it supposed to get the optimal schedule? Should existing meetings in #met.slot be taken into account? I ask this because it's a *very* different problem to do a bulk query to find an optimal schedule (eg, see http://stackoverflow.com/questions/2746309/best-fit-scheduling-algorithm) vs doing one-by-one with a first-come-first-served methodology. — gregmac, Dec 12 '11 at 23:31
@gregmac, you're right on all questions. I updated the question with the right slots — Benny, Dec 13 '11 at 01:20
As far as your second comment, I only need something simple. Just the first opportunity for each "staged" meeting. I don't need first come first serve or anything other than first available without being booked twice in the same slot. — Benny, Dec 13 '11 at 01:23

score 0 · Answer 1 · answered Mar 08 '12 at 06:27

Here is a somewhat iterative process I came up with:

with poss(opt, r1, r2, slot) AS
(
    SELECT
        ROW_NUMBER() OVER(PARTITION BY m.reg1, m.reg2 ORDER BY s1.start),
        m.reg1, m.reg2, s1.slot
    FROM #Met m
    INNER JOIN #Av r1 ON m.reg1 = r1.reg
    INNER JOIN #Slot s1 ON r1.slot = s1.slot
    INNER JOIN #Av r2 ON m.reg2 = r2.reg
    INNER JOIN #Slot s2 ON r2.slot = s2.slot
    WHERE r1.slot = r2.slot
)
, cs as (
    SELECT
        reg1, reg2, e.slot
        , cr=checksum(reg1,reg2)
        , cs1=checksum(reg1,e.slot)
        , cs2=checksum(reg2,e.slot)
        , rn=row_number()over(order by e.slot,reg1,reg2)
    FROM poss e
    INNER JOIN #met m ON e.r1 = m.reg1 AND e.r2 = m.reg2
)
select *
into #poss
from cs
order by rn
go

select top 0 * into #poss1 --this will hold the final results
from #poss

declare @i int=1;

while @i <= (select count(*) from #Met) begin
    insert into #poss1
    select * from #poss p
    where not exists(select 1 from #poss (nolock) where (cr=p.cr or cs1=p.cs1 or cs2=p.cs2) and rn<p.rn)
    and p.rn=@i
    order by slot, reg1, reg2
    set @i+=1;
end;

while @i <= (select count(*) from #poss) begin
    insert into #poss1
    select * from #poss p
    where not exists(select 1 from #poss1 (nolock) where (cr=p.cr or cs1=p.cs1 or cs2=p.cs2))
    and p.rn=@i;
    set @i+=1;
end;
go

select reg1, reg2, slot from #poss1
go

Result:

enter image description here

TSQL Exhaust Available Slots

1 Answers1