Verify if meeting datetime ranges overlap in an IEnumerable list of meetings

Question

I have an assignment where I need to find out if any of the meetings in a list of meeting class object have overlapping datetime ranges. What I have so far is this:

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

    public Meeting(DateTime start, DateTime end)
    {
        this.Start = start;
        this.End = end;
    }
}

public static class StaffMeetings
{
    public static bool DoesNotOverlap(IEnumerable<Meeting> meetings)
    {
        DateTime start = new DateTime();
        DateTime end = new DateTime();
        foreach (Meeting meeting in meetings)
        {
            if (start != DateTime.MinValue && end != DateTime.MinValue)
            {
                if (start < meeting.End && end > meeting.Start)
                {
                    return false;
                }
            }
            start = meeting.Start;
            end = meeting.End;
        }
        return true;
    }

    public static void Main(string[] args)
    {
        var format = System.Globalization.CultureInfo.InvariantCulture.DateTimeFormat;

        Meeting[] meetings = new Meeting[]
        {
        new Meeting(DateTime.Parse("1/1/2015 20:00", format), DateTime.Parse("1/1/2015 21:30", format)),
        new Meeting(DateTime.Parse("1/1/2015 21:30", format), DateTime.Parse("1/1/2015 23:00", format)),
        new Meeting(DateTime.Parse("1/1/2015 23:10", format), DateTime.Parse("1/1/2015 23:30", format))
        };

        Console.WriteLine(StaffMeetings.DoesNotOverlap(meetings));
    }
}

Using the provided data set, I get the correct result but as I add more meetings, my results start to fail and performance drops.

I feel that the problem is in how I am iterating the list. However, if I sort the list first, I can most likely improve reliability but my performance would probably drop. I feel that there should be an algorithm for this, but so far, I have not had any luck finding one.

Answer 1

Without sorting this does not fail and it should
The second and last conflict

new Meeting(DateTime.Parse("1/1/2015 21:30", format), DateTime.Parse("1/1/2015 23:00", format)),
new Meeting(DateTime.Parse("1/1/2015 23:10", format), DateTime.Parse("1/1/2015 23:30", format)),
new Meeting(DateTime.Parse("1/1/2015 20:00", format), DateTime.Parse("1/1/2015 21:30", format)),
new Meeting(DateTime.Parse("1/1/2015 22:10", format), DateTime.Parse("1/1/2015 22:20", format)),
new Meeting(DateTime.Parse("1/1/2015 23:20", format), DateTime.Parse("1/1/2015 23:50", format))

maybe something like this

public class Meeting
{
    public DateTime Start { get; private set; }
    public DateTime End { get; private set; }
    public Meeting(DateTime start, DateTime end)
    {
        this.Start = start;
        this.End = end;
    }
}
public static class StaffMeetings
{
    public static bool DoesNotOverlap(IEnumerable<Meeting> meetings)
    {
        DateTime endPrior = DateTime.MinValue;
        foreach (Meeting meeting in meetings.OrderBy(x => x.Start))
        {
            if (meeting.Start > meeting.End)
                return false;
            if (meeting.Start < endPrior)
                return false;
            endPrior = meeting.End;
        }
        return true;
    }
    public static void Main(string[] args)
    {
        var format = System.Globalization.CultureInfo.InvariantCulture.DateTimeFormat;

        Meeting[] meetings = new Meeting[]
        {
            new Meeting(DateTime.Parse("1/1/2015 21:30", format), DateTime.Parse("1/1/2015 23:00", format)),
            new Meeting(DateTime.Parse("1/1/2015 23:10", format), DateTime.Parse("1/1/2015 23:30", format)),
            new Meeting(DateTime.Parse("1/1/2015 20:00", format), DateTime.Parse("1/1/2015 21:30", format)),
            new Meeting(DateTime.Parse("1/1/2015 22:10", format), DateTime.Parse("1/1/2015 22:20", format)),
            new Meeting(DateTime.Parse("1/1/2015 23:20", format), DateTime.Parse("1/1/2015 23:50", format))
        };

        System.Diagnostics.Debug.WriteLine(StaffMeetings.DoesNotOverlap(meetings));
        Console.WriteLine(StaffMeetings.DoesNotOverlap(meetings));
    }
}

Answer 2

Sorting is what actually makes it work but if you also want it to be more linq-ish and more solid then you should change the following things:

• move the overlap-logic into another method
• change the method to return an IEnumerable<Meeting[]> for meetings that overlap
• use Any to find out whether any meeting overlap
• make both methods extensions

Example:

public static IEnumerable<Meeting[]> Overlappings(this IEnumerable<Meeting> meetings)
{
    var last = (Meeting)null;
    foreach (var meeting in meetings.OrderBy(m => m.Start))
    {
        if (last != null && meeting.OverlapsWith(last))
        {
            yield return new [] { last, meeting };
        }
        last = meeting;
    }
}

public static bool OverlapsWith(this Meeting x, Meeting y) 
{
    return x.Start < y.Start ? x.End > y.Start : y.End > x.Start;
}

Gets overlapping meetings:

var overlappingMeetings = meetings.Overlappings();

or checks if there are any. It stops at the first overlapping pair found:

var meetingsOverlap = meetings.Overlappings().Any();

with these new extensions you are more flexible because you can easily check any two meetings overlap and it's easier to undestand than DoesNotOverlap. Usually it's better to write positive conditions and negate them if necessary rather than the other way around.

---

But even this could be further improved by overloading the two < and > operators:

public static bool operator <(Meeting x, Meeting y) 
{
    return x.End < y.Start;
}

public static bool operator >(Meeting x, Meeting y)
{
    return x.End > y.Start;
}

and making the OverlapsWith method still more natural:

public static bool OverlapsWith(this Meeting x, Meeting y) 
{
    return x.Start < y.Start ? x < y : y > x;
}

Answer 3

You are going to want to make sure that you don't have a meeting with a beginning DateTime more than the ending DateTime. my suggestion would be to throw an exception when something tries to create a meeting with an end time before the start time.

so your Meeting now looks like this

public DateTime Start { get; private set; }
public DateTime End { get; private set; }

public Meeting(DateTime start, DateTime end)
{
    if (end < start)
    {
        throw new ArgumentException("Cannot create a meeting that ends before it starts.");
    }
    this.Start = start;
    this.End = end;
}

I would have something built into the interface for inputting the meetings to make sure that the End does not come before the Start, so in other words I would have some validation on my input.

I like @t3chb0t's approach with the Linq, but some things were a little mixed up

with a little help from a good Code Reviewer I realized that the Static Boolean method OverlapsWith should be inside the Meeting class there is no need for extension here.

I also changed some of the variables to make the code easier to read, I changed the variable named last to first because it is really the first meeting and that cleared up a bug in @t3chb0t's code. When I ran the code I saw that the 2 meetings were mixed up (first one was y and second one was x) and it made the code not work

Here is my code dump from LINQPad

{
    var format = System.Globalization.CultureInfo.InvariantCulture.DateTimeFormat;
    Meeting[] meetings = new Meeting[]
    {
        new Meeting(DateTime.Parse("1/1/2015 21:30", format), DateTime.Parse("1/1/2015 23:00", format)),
        new Meeting(DateTime.Parse("1/1/2015 23:10", format), DateTime.Parse("1/1/2015 23:30", format)),
        new Meeting(DateTime.Parse("1/1/2015 20:00", format), DateTime.Parse("1/1/2015 21:30", format)),
        new Meeting(DateTime.Parse("1/1/2015 22:10", format), DateTime.Parse("1/1/2015 22:20", format)),
        new Meeting(DateTime.Parse("1/1/2015 23:20", format), DateTime.Parse("1/1/2015 23:50", format)),
        new Meeting(DateTime.Parse("1/1/2015 23:20", format), DateTime.Parse("1/2/2015 00:00", format))
    };

    var overlappingMeetings = meetings.Overlappings();
    var meetingsOverlap = meetings.Overlappings().Any();
    overlappingMeetings.Dump();
    meetingsOverlap.Dump();
}

public static class StaffMeetings
{
    public static IEnumerable<Meeting[]> Overlappings(this IEnumerable<Meeting> meetings)
    {
        var first = (Meeting)null;
        foreach (var meeting in meetings.OrderBy(m => m.Start))
        {
            if (first != null && meeting.OverlapsWith(first))
            {
                yield return new [] { first, meeting };
            }
            first = meeting;
        }
    }
}
public class Meeting
{
    public DateTime Start { get; private set; }
    public DateTime End { get; private set; }

    public Meeting(DateTime start, DateTime end)
    {
        if (end < start)
        {
            throw new ArgumentException("Cannot create a meeting that ends before it starts.");
        }
        this.Start = start;
        this.End = end;
    }
    
    public bool OverlapsWith(Meeting first) 
    {
        return first.End > this.Start;
    }
}

---

Better Code

I decided to go a little bit further and see if I could make it so that if you had multiple meetings that started at the same time or multiple meetings during the time of one meeting that it would still show all the overlapping meetings.

I ran into an issue where it would check the meeting against itself so I changed the way I compared the meetings in the Overlappings extension method. So here is what I did:

• I moved the queries to their own variables to make it easier to work with.

• I also created a new List<Meeting> so that I had a way of marking off all the meetings that I had already checked so that I was not checking two meetings in reverse order.

• I created a LINQ query to get all the unchecked meetings and I named it appropriately

Here is what the Overlappings method looks like now.

public static IEnumerable<Meeting[]> Overlappings(this IEnumerable<Meeting> meetings)
{
    var first = (Meeting)null;
    var orderedMeetings = meetings.OrderBy(m => m.Start);
    var checkedMeetings = new List<Meeting>();
    
    foreach (var meeting in orderedMeetings)
    {
        if (first != null)
        {
            checkedMeetings.Add(first);
            var uncheckedMeetings = orderedMeetings.Where(x => (x.Start >= first.Start && !(x == first)) && !checkedMeetings.Any(m => m == x));
            
            foreach (var meet in uncheckedMeetings)
            {
                if (first.OverlapsWith(meet))
                {
                    yield return new[] { first, meet };
                }
            }
        }
        first = meeting;
    }
}

this allows me to run this set of Meetings

    Meeting[] meetings = new Meeting[]
    {
        new Meeting(DateTime.Parse("1/1/2015 21:30", format), DateTime.Parse("1/1/2015 23:00", format)),
        new Meeting(DateTime.Parse("1/1/2015 23:10", format), DateTime.Parse("1/1/2015 23:30", format)),
        new Meeting(DateTime.Parse("1/1/2015 20:00", format), DateTime.Parse("1/1/2015 21:30", format)),
        new Meeting(DateTime.Parse("1/1/2015 22:10", format), DateTime.Parse("1/1/2015 22:20", format)),
        new Meeting(DateTime.Parse("1/1/2015 23:20", format), DateTime.Parse("1/1/2015 23:50", format)),
        new Meeting(DateTime.Parse("1/1/2015 23:20", format), DateTime.Parse("1/2/2015 00:00", format)),
        new Meeting(DateTime.Parse("1/2/2015 09:00", format), DateTime.Parse("1/2/2015 12:00", format)),
        new Meeting(DateTime.Parse("1/2/2015 09:00", format), DateTime.Parse("1/2/2015 10:00", format)),
        new Meeting(DateTime.Parse("1/2/2015 11:00", format), DateTime.Parse("1/2/2015 11:30", format))
    };

and get these results