11
\$\begingroup\$

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

Overlapping meeting results

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)

\$\endgroup\$
  • \$\begingroup\$ Performance-wise, I think you can find overlapping meetings in \$O(N)\$ and not \$O(n^2)\$. About Linq, make sure you understand how it works. From what i remember it doesn't perform the query until it have to, so this can be \$n^2\$ instead of \$2n\$ when performing a query on query. \$\endgroup\$ – shanif Oct 20 '16 at 17:04
  • 2
    \$\begingroup\$ I'm not sure if I should edit your question or not but didn't you forget to copy the void Main()? It's not a copy&paste yet ;-) \$\endgroup\$ – t3chb0t Oct 20 '16 at 17:38
  • \$\begingroup\$ in LINQPad 5 I didn't need it to run the code...lol \$\endgroup\$ – Malachi Oct 20 '16 at 17:45
  • \$\begingroup\$ wow, I didn't know you could define classes in the Statement(s) mode - this explains the missing Main. \$\endgroup\$ – t3chb0t Oct 20 '16 at 17:46
  • 1
    \$\begingroup\$ @njzk2 that would be a good thing to mention in a review. \$\endgroup\$ – Malachi Oct 21 '16 at 13:00
5
\$\begingroup\$

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})";
    }
}

Meetings result

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();
        }
    }
\$\endgroup\$
  • \$\begingroup\$ I am kind of curious if you could do the same thing with DateTime variables? ... \$\endgroup\$ – Malachi Nov 14 '16 at 17:22
  • 1
    \$\begingroup\$ @Malachi sure, you just use the DateTime.Ticks Property that: Gets the number of ticks that represent the date and time of this instance. There is also a special construtor that you can pass ticks. \$\endgroup\$ – t3chb0t Nov 14 '16 at 17:27
  • 1
    \$\begingroup\$ Be sure to implement a good Equals and HashCode, HashSet makes use of those. \$\endgroup\$ – Bruno Costa Dec 4 '16 at 10:34
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Sorry, need to run to get my train. Maybe I will add more tomorrow. \$\endgroup\$ – Heslacher Oct 20 '16 at 16:45
  • \$\begingroup\$ I was thinking this didn't really do anything, I was going to add a Title and a Guid for an ID, but the ID didn't feel right... good answer, thank you \$\endgroup\$ – Malachi Oct 20 '16 at 16:47
  • \$\begingroup\$ Call base inside override \$\endgroup\$ – radarbob Oct 20 '16 at 21:04
4
\$\begingroup\$

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();
    }
}
\$\endgroup\$
  • \$\begingroup\$ these methods were left over from my thoughts of having more than one meeting with the same start and end times. I should have taken them out because I didn't give a way to specify the title which is something else I was thinking about in one of my versions with the overridden methods. in this case your equality wouldn't work for what I was going to do. other than that I like the methods and recognize the GetHashCode() method \$\endgroup\$ – Malachi Oct 21 '16 at 1:27
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I think that my next attempt will look something like @t3chb0t's answer, I like his idea, have you taken a look at his answer? \$\endgroup\$ – Malachi Dec 5 '16 at 13:49
  • \$\begingroup\$ Also did you see my "selfie" answer? I am not sure if this makes the complexity any better though. it might be slightly better, if any. \$\endgroup\$ – Malachi Dec 5 '16 at 13:52
  • \$\begingroup\$ sorting a sequence of items is O(n*log(n)), not O(n). Additionally, the OP's code re-orders and re-searches through the code for each item in the sequence, so the end result is O((n^2)*log(n)). \$\endgroup\$ – Servy Dec 5 '16 at 19:06
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ the !(x==first) makes sure we aren't checking the meeting against itself, but would still allow checking the meeting against already checked meetings. the whole point was to check if there were multiple meetings that overlapped a single meeting, and a meeting that overlapped one meeting but not another that overlapped it. please see the example meetings that I used to test my code. \$\endgroup\$ – Malachi Oct 20 '16 at 17:36
  • \$\begingroup\$ Not getting how an already checked meeting could be in there. You just added first and have a condition (x.Start >= first.Start && !(x == first)) and orderedMeetings is ordered \$\endgroup\$ – paparazzo Oct 20 '16 at 17:41
  • \$\begingroup\$ if I remove !checkedMeetings.Any(m => m == x) then I get 2 extra meeting overlaps that are repeats of other checks. it doesn't work. punch the code into LinqPad or whatever and run the code. \$\endgroup\$ – Malachi Oct 20 '16 at 17:48
  • \$\begingroup\$ that query says grab the meetings that start at the same time as this meeting or any meeting in the future and do not grab this current meeting and do not grab meetings that we already checked I can see where you are confused now. I put 2 meetings in there that start at the same time, if there are multiple meetings that start at the same time it keeps the algorithm from checking the 2 meetings against each other in reverse. \$\endgroup\$ – Malachi Oct 20 '16 at 17:55
  • \$\begingroup\$ It is an expensive check. \$\endgroup\$ – paparazzo Oct 20 '16 at 18:00
1
\$\begingroup\$

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.

\$\endgroup\$

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.