Comparing DateTime structs to find free slots

Question

I would like to search through the events of all of the users in a list and retrieve all times where every user is free of 30mins or greater between 7AM-7PM.

There is a catch however, if a method is marked as 'recurring', ie the bit recurring is set to 1, then that event recurs for a period of 52 weeks after its beginning (so the time is not available). Retrieval of these events are taken care of in a stored procedure.

My code so far is below. Am I going about writing this procedure the right way? I'm not really sure how to proceed to get the function to return as I would like. Would anyone be able to help me with this?

List<string> usernames = //List of usernames.
DateTime start = //DateTime for start of period you would like to schedule meeting
DateTime end = //DateTime for end of period
//int mins = //duration of meeting (must be 30mins or greater)

foreach (string username in usernames) {
   //retrieve events for this user
    var db = Database.Open("mPlan");
    List<DateTime> startTimes;
    List<DateTime  endTimes;
    // This stored procedure returns all events of a user in a given time period, 
    // including recurring events.
    var record = db.Query("EXEC dbo.GetEvents @0, @1, @2", username, start, end);
    foreach(var record in result) {
          startTimes.Add(record.event_start);
          endTimes.Add(record.event_end);
    }
    // so now I have a list of all start times and end times of events
    // for one user and could save all this data in a list
  }

Table structure:

DECLARE @Users TABLE
(    
    UserID   INT IDENTITY(1,1),
    Username VARCHAR(32)
);

DECLARE @Groups TABLE
(
    GroupID   INT IDENTITY(1,1),
    GroupName VARCHAR(32)
);

DECLARE @Membership TABLE
(
    UserID  INT,
    GroupID INT
);

DECLARE @event TABLE
(
    event_id    INT IDENTITY(1,1),
    event_start DATETIME,
    event_end   DATETIME,
    group_id    INT,
    recurring   BIT
);

Example of functionality I would like :

User adds multiple users from the database to a list. User selects a time period over which he would like to have a meeting with all of these users. My algorithm computes all time periods that are free for all users (i.e a times that would be suitable to have a meeting between all users and are >30mins ).

Additional information :

Sample cases :

• User A attempts to organize a meeting with User B. All timeslots are free. I would like the algorithm to return a DateTime start and DateTime end of all possible combinations of start times and end times that are >30mins and == duration ( a parameter ).

• Typical case : User A has events planned for all times except 6pm - 7pm. He attempts to organize a meeting with user B for duration of 1 hour. User B has no events organized - the DateTime 6PM and DateTime 7pm are returned to indicate the start and end time of meetings.

• Recurring case : User A has a recurring event at 5pm-6pm on a Monday. He tries to organize a meeting of 2 hours on a monday in six weeks time. All combinations of DateTime start and DateTime end where there is a difference of 2 hours are returned. The time 5pm-7pm is not returned, since this event is recurring and occurs every week for 52 weeks.

Here is the stored procedure which retrieves all of a users events for a set time period (start, end):

ALTER PROCEDURE dbo.GetEvents 
  @UserName VARCHAR(50), 
  @StartDate DATETIME, 
  @EndDate DATETIME 
AS 

BEGIN 
-- DEFINE A CTE TO GET ALL GROUPS ASSOCIATED WITH THE CURRENT USER 
;WITH Groups AS  
(   SELECT  GroupID  
    FROM    Membership  m 
            INNER JOIN Users u 
                ON m.UserID = u.UserID 
    WHERE   Username = @UserName 
    GROUP BY GroupID 
), 
-- DEFINE A CTE TO GET ALL EVENTS FOR THE GROUPS DEFINED ABOVE 
AllEvents AS 
(   SELECT  e.* 
    FROM    event e 
            INNER JOIN Groups m  
                ON m.GroupID = e.group_id 
    UNION ALL 
    SELECT  e.event_id, e.title, e.description, 
      DATEADD(WEEK, w.weeks, e.event_start), 
      DATEADD(WEEK, w.weeks, e.event_end), 
      e.group_id, e.recurring 
    FROM    event e 
            INNER JOIN Groups m  
                ON m.GroupID = e.group_id 
            CROSS JOIN  
            (   SELECT  ROW_NUMBER() OVER (ORDER BY Object_ID) AS weeks 
                FROM    SYS.OBJECTS 
            ) AS w 
    WHERE  e.recurring = 1 
)    
-- GET ALL EVENTS WHERE THE EVENTS FALL IN THE PERIOD DEFINED 
SELECT  * 
FROM    AllEvents 
WHERE   Event_Start >= @StartDate 
AND     Event_End <= @EndDate 

END 

Answer 1

So imagine some tables:

USE tempdb;
GO

CREATE TABLE dbo.Users
(    
    UserID   INT IDENTITY(1,1),
    Username VARCHAR(32)
);

CREATE TABLE dbo.Groups
(
    GroupID   INT IDENTITY(1,1),
    GroupName VARCHAR(32)
);

CREATE TABLE dbo.Membership
(
    UserID  INT,
    GroupID INT
);

CREATE TABLE dbo.[event]
(
    event_id    INT IDENTITY(1,1),
    event_start DATETIME,
    event_end   DATETIME,
    group_id    INT,
    recurring   BIT
);

And imagine that some sample data weren't so difficult to provide:

INSERT dbo.Users(Username) 
    SELECT 'User A' UNION ALL SELECT 'User B';

INSERT dbo.Groups(GroupName) 
    SELECT 'Group 1' UNION ALL SELECT 'Group 2';

INSERT dbo.Membership(UserID, GroupID)
    SELECT 1,1 UNION ALL SELECT 2,2;


INSERT dbo.[event](event_start, event_end, group_id, recurring)
-- user A, almost all day meeting on a specific date
SELECT '20120313 07:00', '20120313 18:00', 1, 0 

-- user A, recurring meeting every Monday
UNION ALL SELECT '20120312 17:00', '20120312 18:00', 1, 1 

-- user A, recurring meeting every Tuesday (future)
UNION ALL SELECT '20120327 14:00', '20120327 15:00', 1, 1; 
GO

Now we can build this stored procedure:

CREATE PROCEDURE dbo.GetPossibleMeetingTimes
    @AskingUserID INT,
    @TargetUserID INT,
    @Duration     INT,           -- in minutes!
    @StartDate    SMALLDATETIME, -- assumes date, no time!
    @EndDate      SMALLDATETIME  -- again - date, no time!
AS
BEGIN
    SET NOCOUNT ON;

    ;WITH dRange(d) AS
    (
        -- get the actual dates in the requested range
        -- limited to number of rows in sys.objects

        SELECT TOP (DATEDIFF(DAY, @StartDate, @EndDate)+1) 
            DATEADD(DAY, n-1, @StartDate)
         FROM (SELECT n = ROW_NUMBER() OVER (ORDER BY [object_id])
          FROM sys.objects) AS x
    ), possible(ds, de) AS
    (
        -- get all the timeslots of @Duration minutes 
        -- between 7:00 AM and 7:00 PM for each day in 
        -- the range - these are all *potential* slots

        SELECT DATEADD(MINUTE, 30*rn, DATEADD(HOUR, 7, dRange.d)),
            DATEADD(MINUTE, 30*rn + @Duration, DATEADD(HOUR, 7, dRange.d))
        FROM (SELECT TOP (720/30) rn = ROW_NUMBER() OVER
        (ORDER BY [object_id])-1 FROM sys.objects) AS x
        CROSS JOIN dRange
    )
    SELECT p.ds, p.de FROM possible AS p 
    WHERE p.de <= DATEADD(HOUR, 19, DATEADD(DAY, DATEDIFF(DAY, 0, p.de), 0)) 
    AND NOT EXISTS 
    (
        SELECT 1 FROM 
        (
            -- filter down to users with events on the days in the range

            SELECT group_id, event_start, event_end
                FROM dbo.[event] 
                WHERE event_start >= @StartDate 
                AND event_start < DATEADD(DAY, 1, @EndDate)
            UNION ALL 

            -- also include users with recurring events on same weekday(s)
            -- normalized to the matching day in the range

            SELECT group_id, 
              event_start = DATEADD(DAY, DATEDIFF(DAY, event_start, p.ds), event_start),
              event_end   = DATEADD(DAY, DATEDIFF(DAY, event_end,   p.ds), event_end)
            FROM dbo.[event]
            WHERE recurring = 1 
            AND event_start <= DATEADD(DAY, 1, @EndDate) -- ignore future events
                    AND event_start >= DATEADD(WEEK, -52, @EndDate) -- 52 weeks out 
            AND DATEDIFF(DAY, event_start, p.ds) % 7 = 0 -- same weekday
        ) AS sub
        WHERE sub.group_id IN 
        (
            -- this checks that events are within previously scheduled times

            SELECT GroupID FROM dbo.Membership
              WHERE UserID IN (@AskingUserID, @TargetUserID)
              AND (p.de > sub.event_start AND p.ds < sub.event_end)
        )
    )
    ORDER BY p.ds, p.de;
END
GO

Example calls:

-- Case 1: User A tries to meet with User B on a day where 
-- both schedules are clear.

EXEC dbo.GetPossibleMeetingTimes
    @AskingUserID = 1,
    @TargetUserID = 2,
    @Duration     = 30,
    @StartDate    = '20120314', -- no events for either user
    @EndDate      = '20120314';

Results:

-- Case 2: User A tries to meet with User B for an hour, on 
-- a day where user A has meetings from 7 AM to 6 PM.

EXEC dbo.GetPossibleMeetingTimes
    @AskingUserID = 1,
    @TargetUserID = 2,
    @Duration     = 60,
    @StartDate    = '20120313', -- user A has an almost all-day event
    @EndDate      = '20120313';

Results:

-- Case 3: User A tries to meet with User B for two hours, on 
-- a weekday where User A has a recurring meeting from 5-6 PM

EXEC dbo.GetPossibleMeetingTimes
    @AskingUserID = 1,
    @TargetUserID = 2,
    @Duration     = 120,        
    @StartDate    = '20120319', -- user A has a recurring meeting
    @EndDate      = '20120319';

Results:

Now note that I took care of several factors you either haven't considered or haven't mentioned (such as a recurring event that starts in the future). On the other hand, I also didn't deal with some other factors (e.g. daylight savings time, if it may impact this at all) and didn't test all possible scenarios (e.g. multiple events on the same day that already exist).

I did test that if you pass in a range (e.g. 2012-03-12 -> 2012-03-14) you will essentially just get a union of the above results with roughly the same time slots made available (these vary based on duration of course). The important part is that the blackout timeslots are honored. I did not test the logic for the case where a recurring event starts in the future and the provided date range includes that weekday both before and after the first instance of the event.

If any case doesn't work for you, then this is exactly why it's important that you show us all your cases using sample data, not word problems and also explain the desired results of the query given that data.

EDIT - to handle more than 2 users, you only need a few changes. If you add a split function as follows:

CREATE FUNCTION dbo.SplitInts( @List VARCHAR(MAX) )
RETURNS TABLE
AS
   RETURN 
   ( SELECT Item = CONVERT(INT, Item) FROM (
      SELECT Item = x.i.value('(./text())[1]', 'INT') FROM (
       SELECT [XML] = CONVERT(XML, '<i>' + REPLACE(@List, ',', '</i><i>') 
         + '</i>').query('.')) AS a CROSS APPLY [XML].nodes('i') AS x(i)) AS y
       WHERE Item IS NOT NULL
   );

Now very minor changes to the stored procedure (I've left out the unchanged bits):

ALTER PROCEDURE dbo.GetPossibleMeetingTimes
    @UserIDList   VARCHAR(MAX),  -- removed other two parameters
    @Duration     INT,           
    @StartDate    SMALLDATETIME, 
    @EndDate      SMALLDATETIME  
AS
...
        WHERE sub.group_id IN -- changed the code within this subquery
        (
            SELECT GroupID FROM dbo.Membership AS m
              INNER JOIN dbo.SplitInts(@UserIDList) AS i
              ON m.UserID = i.Item
              WHERE (p.de > sub.event_start AND p.ds < sub.event_end)
        )
...

So then your call just changes slightly to:

EXEC dbo.GetPossibleMeetingTimes
     @UserIDList = '1,2,3,4,5',
     @Duration   = 30,
     @StartDate  = '20120314',
     @EndDate    = '20120314';

Just make sure that the requester is included in the comma-separated list.

PS this addendum is untested.