Find all the common time from List of time provided by each user

Question

I had asked this question previously. The idea is same except that I have to find all the common time within certain TimeSpan.

Background

Lets suppose,

I want to meet some peoples, and I say I want to meet certain peoples between Datetime X(2014-02-16 09:00:00.000) to DateTime Y(2014-02-26 05:00:00.000). And I say I want to the meeting to last for at least N number of hours.

Then the peoples i want to meet with will reply saying i will be available in following dates:

Date1(Certain date from certain start time to certain end time), 

Date2(certain date from certain time to certain time),

...

and so on.

Objective

I then have to find if there exists a time range that includes in all the user's response.

Lets consider these are the responses

Attendee1(Some GuidId):

Response1: Start Time=2014-02-23 09:00 AM, EndTime = 2014-02-23 11:00 AM,

Response2 : Start Time=2014-02-24 10:00 AM, EndTime = 2014-02-24 12:00 PM,

Response3 : Start Time=2014-02-25 10:00 AM, EndTime = 2014-02-25 11:00 AM,

Response4 : Start Time=2014-02-23 01:00 PM, EndTime = 2014-02-17 5:00 PM

Attendee2(Some GuidId):

Response1: Start Time=2014-02-22 09:00 AM, EndTime = 2014-02-22 05:00 PM,

Response2 : Start Time=2014-02-23 09:00 AM, EndTime = 2014-02-23 05:00 PM,

Response3 : Start Time=2014-02-25 09:00 AM, EndTime = 2014-02-25 12:00 PM,

Attendee3(Some GuidId):

Response1: Start Time=2014-02-22 11:00 AM, EndTime = 2014-02-22 02:00 PM,

Response2 : Start Time=2014-02-23 04:00 PM, EndTime = 2014-02-23 03:00 PM,

Response3 : Start Time=2014-02-23 4:30 PM, EndTime = 2014-02-23 05:30 PM,

Response4 : Start Time=2014-02-24 02:00 AM, EndTime = 2014-02-24 05:00 PM,

Response5 : Start Time=2014-02-25 11:00 AM, EndTime = 2014-02-25 12:00 PM,

So, if possible, I should come up with something that will say here are the matches found, if not then just find if the common time exists for all the user's or not.

Time X to Time Y (Difference between X and Y should be at least the TimeSpan mentioned) : Number of Attendee in this match = N(type = int, 1 or 2 or as many match as found)

Time A to Time B : Number of Attendee in this match = N

...

etc.

PS:

It is a MVC 5.1 application and database is created using code first approach. So in database there is table called Appointment which stores the StartDateTime and EndDateTime

Here are my DataModels

public class Appointment
{

    [Key]
    public Guid Id { get; set; }

    public virtual ICollection<Attendee> Attendees { get; set; }

    public DateTime StartDateTime { get; set; }
    public DateTime EndDateTime { get; set; }    
    public TimeSpan MinAppointmentDuration { get; set; }  

}

and between these dates people(Attendee) attending will give their response. Each person(who will respond), their information is stored in database table called Attendees

public class Attendee
{
    public Guid AttendeeId { get; set; }
    public virtual ICollection<Response> Responses { get; set; } 
}

And for each user their response is stored in Responses table whose model would look like

public class Response
{
    [Key]
    [DatabaseGenerated(DatabaseGeneratedOption.Identity)]
    public int Id { get; set; }
    public Guid AttendeeId { get; set; }
    public DateTime StartDateTime { get; set; }
    public DateTime EndDateTime { get; set; }

}

This is what I have done but it doesn't work.

public class CommonTime
{
    public DateTime Start { get; set; }
    public DateTime End { get; set; }
    public TimeSpan MinAppointmenttime { get; set; }
    public int NumAttendees 
    { 
        get { return Responses.Select(x => x.AttendeeId).Distinct().Count(); } 
    }
    public List<DataModels.Response> Responses { get; set; }

    public CommonTime(DataModels.Response response, TimeSpan time)
    {
        Responses = new List<DataModels.Response>();
        Start = response.StartDateTime;
        End = response.EndDateTime;
        MinAppointmenttime = time;
    }

    public void MergeCommonTime(DataModels.Response response)
    {
        if(Start <= response.StartDateTime && response.EndDateTime<=End)
        {
            Start = response.StartDateTime;
            End = response.EndDateTime;
            if((End-Start)>=MinAppointmenttime)
            {
                Responses.Add(response);
            }

        }
    }

    public List<CommonTime> FindCommonMatches(Guid appointmentId)
    {
        var appointment = _db.Appointments.Find(appointmentId);
        var attendees = appointment.Attendees.ToList();
        var matches = new List<CommonTime>();
        bool isFirstAttendee = true;
        foreach (var attendee in attendees)
        {
            if (isFirstAttendee)
            {
                foreach (var response in attendee.Responses)
                {
                    matches.Add(new CommonTime(response, appointment.MinAppointmentDuration));

                }
                isFirstAttendee = false;
            }
            else
            {
                foreach (var response in attendee.Responses)
                {
                    matches.ForEach(x => x.MergeCommonTime(response));
                }
            }
        }

        return matches;
    }

}

So in this case if Attendee X(with some Guid Id) gives his/her availability as

and Attendee Y gives his/her availibility as

this is the common match I get

Which is not what I want as I explained.

So, what should I do to get what I want.

---

Edit:

Based upon Answer from Zache

    public class Meeting
    {
        public DateTime Start { get; set; }
        public DateTime End { get; set; }

        public List<DataModels.Attendee> Attendees { get; set; }

    }

    public class Requirement
    {
        public DateTime Start { get; set; }
        public DateTime End { get; set; }

        public TimeSpan MinHours { get; set; }

        public int MinAttendees { get; set; }

        public IEnumerable<Meeting> Meetings()
        {
            var possibleMeetings = new List<Meeting>();
            var availableHours = (End - Start).TotalHours;

            for (var i = 0; i < availableHours - MinHours.Hours; i++)
                yield return new Meeting
                {
                    Start = Start.AddHours(i),
                    End = Start.AddHours(i+MinHours.Hours)
                };
        }
    }

    public class Scheduler
    {
        public IEnumerable<Meeting> Schedule(Requirement req, List<DataModels.Attendee> attendees)
        {
            var fullMatches = new List<Meeting>();
            var partialMatches = new List<Meeting>();

            foreach (var m in req.Meetings())
            {
                foreach (var a in attendees)
                {
                    if (fullMatches.Any())
                    {
                        if (a.Responses.Any(r => r.StartDateTime <= m.Start && r.EndDateTime >= m.End))
                        {
                            if (m.Attendees == null)
                            {
                                m.Attendees = new List<DataModels.Attendee> { a };
                            }
                            else
                            {
                                m.Attendees.Add(a);
                            }
                        }
                        else
                        {
                            break; // If we found one full match we aren't interested in the partials anymore.
                        }
                    }
                    else
                    {
                        if (a.Responses.Any(r => r.StartDateTime <= m.Start && r.EndDateTime >= m.End))
                        {
                            if (m.Attendees == null)
                            {
                                m.Attendees = new List<DataModels.Attendee> { a };
                            }
                            else
                            {
                                m.Attendees.Add(a);
                            }
                        }
                    }
                }

                if (m.Attendees != null)
                {
                    if (m.Attendees.Count == attendees.Count)
                        fullMatches.Add(m);
                    else if (m.Attendees.Count >= req.MinAttendees)
                        partialMatches.Add(m);
                }
            }

            return fullMatches.Any() ? fullMatches : partialMatches;
        }
    }
}

in repository

public IEnumerable<Meeting> FindCommonMatches(Guid appointmentId)
{
    var appointment = _db.Appointments.Find(appointmentId);
    var attendees = appointment.Attendees.Where(a => a.HasResponded == true).ToList();
    var req = new Requirement
    {
        Start = appointment.StartDateTime,
        End = appointment.EndDateTime,
        MinHours = appointment.MinAppointmentDuration,
        MinAttendees = 1
    };
    var schedule = new Scheduler();
    var schedules = schedule.Schedule(req, attendees);
    return schedules;
 }

StartDate: 2/24/2014 11:30:00 AM//that I set while creating appointment

EndDate: 2/25/2014 11:30:00 AM

When the first user responds with following data:

matches result:

when second attendee responds with following data

matches result

Here the common matches should have been:

Match1: 2/24/2014 10:00:00 AM   to   2/24/2014 11:00:00 AM
 Match2: 2/25/2014 9:00:00 AM   to   2/25/2014 11:00:00 AM

Answer 1

The following GetMeetingWindows function will return a list of all matching windows and available attendees. Full or minimum attendee stipulations can then be applied as required on the result e.g.

GetMeetingWindows(attendees, TimeSpan.FromMinutes(60)).Where(x => x.AvailableAttendees.Count() == attendees.Count());

I have assumed the supplied attendee responses have already taken into consideration the overall time frame available for the meeting, but if this is not the case then this restriction can be added as an additional attendee which is then filtered for in the result, e.g.

GetMeetingWindows(...).Where(x => x.AvailableAttendees.Contains(meetingRoom));

The code:

public class Attendee
{
    public ICollection<Response> Responses { get; set; } 
}

public class Response
{
    public DateTime StartDateTime { get; set; }
    public DateTime EndDateTime { get; set; }
}

public class Window
{
    public DateTime StartDateTime { get; set; }
    public DateTime EndDateTime { get; set; }
    public IEnumerable<Attendee> AvailableAttendees { get; set; }   
}

public IEnumerable<Window> GetMeetingWindows(IEnumerable<Attendee> attendees, TimeSpan meetingDuration)
{
    var windows = new List<Window>();
    var responses = attendees.SelectMany(x => x.Responses).Where(x => x.EndDateTime - x.StartDateTime >= meetingDuration);

    foreach(var time in (responses.Select(x => x.StartDateTime)).Distinct())
    {
        var matches = attendees.Select(x => new { 
            Attendee = x, 
            MatchingAvailabilities = x.Responses.Where(y => y.StartDateTime <= time && y.EndDateTime >= time.Add(meetingDuration)) 
        });

        windows.Add(new Window { 
            StartDateTime = time, 
            EndDateTime = matches.SelectMany(x => x.MatchingAvailabilities).Min(x => x.EndDateTime), 
            AvailableAttendees = matches.Where(y => y.MatchingAvailabilities.Any()).Select(x => x.Attendee) 
        });
    }

    foreach(var time in (responses.Select(x => x.EndDateTime)).Distinct())
    {
        var matches = attendees.Select(x => new { 
            Attendee = x, 
            MatchingAvailabilities = x.Responses.Where(y => y.EndDateTime >= time && y.StartDateTime <= time.Add(-meetingDuration)) 
        });

        windows.Add(new Window { 
            EndDateTime = time, 
            StartDateTime = matches.SelectMany(x => x.MatchingAvailabilities).Max(x => x.StartDateTime), 
            AvailableAttendees = matches.Where(y => y.MatchingAvailabilities.Any()).Select(x => x.Attendee) 
        });
    }

    return windows.GroupBy(x => new { x.StartDateTime, x.EndDateTime }).Select(x => x.First()).OrderBy(x => x.StartDateTime).ThenBy(x => x.EndDateTime);
}

public void Test() 
{
    var attendees = new List<Attendee>();
    attendees.Add(new Attendee { Responses = new[] { 
        new Response { StartDateTime = DateTime.Parse("2014-02-24 9:00:00 AM"), EndDateTime = DateTime.Parse("2014-02-24 11:00:00 AM") },
        new Response { StartDateTime = DateTime.Parse("2014-02-24 2:00:00 PM"), EndDateTime = DateTime.Parse("2014-02-24 4:00:00 PM") },
        new Response { StartDateTime = DateTime.Parse("2014-02-25 9:00:00 AM"), EndDateTime = DateTime.Parse("2014-02-25 11:00:00 AM") },
        new Response { StartDateTime = DateTime.Parse("2014-02-25 3:00:00 PM"), EndDateTime = DateTime.Parse("2014-02-25 5:00:00 PM") }
    }});
    attendees.Add(new Attendee { Responses = new[] { 
        new Response { StartDateTime = DateTime.Parse("2014-02-24 10:00:00 AM"), EndDateTime = DateTime.Parse("2014-02-24 11:00:00 AM") },
        new Response { StartDateTime = DateTime.Parse("2014-02-24 4:00:00 PM"), EndDateTime = DateTime.Parse("2014-02-24 5:00:00 PM") },
        new Response { StartDateTime = DateTime.Parse("2014-02-25 9:00:00 AM"), EndDateTime = DateTime.Parse("2014-02-25 11:00:00 AM") }
    }});

    var windows = GetMeetingWindows(attendees, TimeSpan.FromMinutes(60));
    foreach(var window in windows)
    {
        Console.WriteLine(String.Format("Start: {0:yyyy-MM-dd HH:mm}, End: {1:yyyy-MM-dd HH:mm}, AttendeeCount: {2}", window.StartDateTime, window.EndDateTime, window.AvailableAttendees.Count()));
    }
}