Too Many Staff Meetings

Question

I recently got in really deep on a question to find the overlapping meetings and I rewrote a bit of the code and added some things to the code, and I would just like a general review of my code and what I could do to make it even better, maybe performance wise or whatever.

Here is my LINQPad 5 Code Dump, you should be able to copy paste into LINQPad and run it, I don't think I did anything that is too cutting edge.

{
    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)),
        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))
    };

    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;
        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;
        }
    }
}
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 second)
    {
        return this.End > second.Start;
    }
    public override bool Equals(object obj)
    {
        return base.Equals(obj);
    }
    public override int GetHashCode()
    {
        return base.GetHashCode();
    }
}

here are the results of that run as well

Did I miss anything?

Are there more edge cases that I didn't consider?

Is there a nice, neat, acceptable way of streamlining the foreach statements with the if statements inside of them? (Kind of curious if it is possible to one line it)

Answer 1

I had given it a second thought and I came up with another solution. For the sake of simplicity I replaced the DateTime with int.

Particularly I did the following:

• each meeting has two points that can be identified as start or end point
• each point has a parent (its meeting)

These o--o are example meetings that I used for testing. \ and / indicate an overlap.

  o-o    o------o      o----o    o--o
     |    \      |    |    /    |
      o----o      o--o     o---o
                     |     \
                     o------o

          2                3    

The algorithm works like this:

• I don't sort the meetings but add all points to a collection first
• now I sort the points
• I loop over each point and if it's a start point then I add it to the hashset, consecutive start points indicate an overlap; if it's an end point then I dump the hashset if it contains more then one point as a result and clear it

Source:

{
    Meeting[] meetings = new Meeting[]
    {
            new Meeting(4, 6),
            new Meeting(8, 13),
            new Meeting(11, 18),
            new Meeting(20, 23),
            new Meeting(23, 30),
            new Meeting(25, 30),
            new Meeting(29, 33),
            new Meeting(35, 37),
    };

    var overlappingMeetings = meetings.Overlappings();
    var meetingsOverlap = meetings.Overlappings().Any();
    overlappingMeetings.Select(m => m.Select(y => y.ToString())).Dump();
    meetingsOverlap.Dump();
}

public static class StaffMeetings
{
    public static IEnumerable<Meeting[]> Overlappings(this IEnumerable<Meeting> meetings)
    {
        var meetingSet = new HashSet<Meeting>();
        var points = meetings.Select(x => new[] { x.Start, x.End }).SelectMany(x => x).OrderBy(x => x.Value);
        foreach (var point in points)
        {
            switch (point.Type)
            {
                case PointType.Start:
                    meetingSet.Add(point.Parent);
                    break;
                case PointType.End:
                    if (meetingSet.Count > 1)
                    {
                        yield return meetingSet.ToArray();
                    }
                    meetingSet.Clear();
                    break;
            }

        }
    }
}

public enum PointType
{
    Start,
    End
}

public class Point
{
    public Point(int value, PointType type, Meeting parent)
    {
        Value = value;
        Type = type;
        Parent = parent;
    }

    public Meeting Parent { get; }
    public int Value { get; }
    public PointType Type { get; }
}

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

    public Meeting(int start, int end)
    {
        Start = new Point(start, PointType.Start, this);
        End = new Point(end, PointType.End, this);
    }

    public bool OverlapsWith(Meeting second)
    {
        return this.End.Value > second.Start.Value;
    }

    public override string ToString()
    {
        return $"({Start.Value}, {End.Value})";
    }
}

The modified loop returns the same results as the original code:

    foreach (var point in points)
    {
        switch (point.Type)
        {
            case PointType.Start:
                meetingSet.Add(point.Parent);
                break;
            case PointType.End:
                meetingSet.Remove(point.Parent);
                break;
        }
        if (meetingSet.Count == 2)
        {
            yield return meetingSet.ToArray();
        }
    }

Answer 2

Just a quick shot

This

public override bool Equals(object obj)
{
    return base.Equals(obj);
}
public override int GetHashCode()
{
    return base.GetHashCode();
}  

doesn't buy you anything. Overriding a method and the calling the base method is just rubbish which lays around in the codebase.

Answer 3

If you want equality/hashing in a meaningful fashion (not sure if that's a real requirement), here's some boilerplate:

public override bool Equals(object obj)
{
    var second = obj as Meeting;

    return (second != null)
        && ((second.Start == this.Start)
        && (second.End == this.End));
}

public override int GetHashCode()
{
    unchecked
    {
        var hash = 17;

        hash = 23 * hash + this.Start.GetHashCode();
        return 31 * hash + this.End.GetHashCode();
    }
}

Answer 4

I think you can find overlapping meetings in \$O(N)\$. Have you tried?

About LINQ:

Of course it affects the runtime complexity. If you assume that query is \$O(N)\$ but it takes \$O(N^2)\$ then the runtime complexity is different.

This is my analysis:

• var orderedMeetings = meetings.OrderBy(m => m.Start); is \$O(N)\$
• foreach (var meeting in orderedMeetings) is \$O(N)\$
• var uncheckedMeetings = orderedMeetings.Where(....); is \$O(N)\$ or \${O(N^2)}\$

This is the part I am not sure of. This is a query done on query (orderedMeetings is a query). From what I remember it doesn't perform the query until it has to, so this can cause \$n^2\$ instead of \$2n\$ when performing a query on query. When you understand this you will understand the runtime complexity.

Answer 5

Not getting then need for

!checkedMeetings.Any(m => m == x)

You have already checked for

!(x == first)

If you order by Start and then End desc you can stop looking once you find the first non overlap

if (first.OverlapsWith(meet))
{
     yield return new[] { first, meet };
}
else  
{
     break;
}

Answer 6

Because the meetings are ordered and there is a list of already checked meetings, all that is needed is that the already checked meetings are not included when checking more meetings.

this makes the inside query a lot cleaner.

var uncheckedMeetings = orderedMeetings.Where(x => !checkedMeetings.Any(m => m == x));

These pieces of that Query were Redundant

x.Start >= first.Start

And

!(x == first)

so getting rid of them didn't make a difference, it just makes the code cleaner and might make the query a little more efficient.