13
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Please provide data that fails. If you sort you might be able to simplify the test. And you should check that end > start for each meeting \$\endgroup\$ – paparazzo Oct 18 '16 at 20:11
  • \$\begingroup\$ I'd avoid calling methods DoesNotXYZ - it will lead to double negative confusion. \$\endgroup\$ – Jack Marchetti May 8 '19 at 2:24
7
\$\begingroup\$

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));
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ That did the trick. Sorting first using OrderBy Linq operator solved the instability issue and change in the if statement within the foreach seems to have improved performance. Good job! \$\endgroup\$ – Dave Adler Oct 18 '16 at 21:07
  • \$\begingroup\$ @DaveAdler See update for a little more speed \$\endgroup\$ – paparazzo Oct 18 '16 at 21:23
  • \$\begingroup\$ I think that you should merge those two if statements. \$\endgroup\$ – Malachi Oct 19 '16 at 19:30
  • \$\begingroup\$ I posted an answer that reviews the issues with @t3chb0t 's code as well as the issue with input validation. \$\endgroup\$ – Malachi Oct 19 '16 at 21:58
9
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Did you test this. That condition does not look right to me. \$\endgroup\$ – paparazzo Oct 19 '16 at 14:15
  • \$\begingroup\$ Now the order shouldn't matter. \$\endgroup\$ – t3chb0t Oct 20 '16 at 4:04
  • \$\begingroup\$ if you don't order the meetings then you won't be comparing the meetings in the right order. the first meeting in the array might overlap with the last meeting in the array but you won't check that meeting. TL;DR you have to order the meetings. then you have to take into consideration that meeting 2 & 3 overlap meeting 1 but meeting 3 doesn't overlap meeting 2. I am working on a solution for it \$\endgroup\$ – Malachi Oct 20 '16 at 14:37
  • \$\begingroup\$ @Malachi those are too many overlapping ideas at once, I give up ;-] \$\endgroup\$ – t3chb0t Oct 20 '16 at 14:45
  • \$\begingroup\$ Check out my answer and my rags-to-riches question --> codereview.stackexchange.com/q/144790/18427 \$\endgroup\$ – Malachi Oct 20 '16 at 16:44
5
\$\begingroup\$

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

Overlapping Meetings Results from LINQPad 5

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.