Finding overlapping time intervals

Question

You have two lists with meetings scheduling (start time, end time). Meetings in single list don't intersect. Find all intersecting meetings across the two lists.

Is my complexity \$O(N M)\$? If I use binary search I might get \$O(N \log M)\$. Can you think of a better algorithm?

For simplicity, I didn't use DateTime. I just assumed meetings are in round hours.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{

    public class IntersectingMeetings
    {
        public IntersectingMeetings()
        {
            MeetingList meetingList1 = new MeetingList();
            MeetingList meetingList2 = new MeetingList();
            meetingList1.AddMeeting(2,3);
            meetingList1.AddMeeting(1,2);

            meetingList1.AddMeeting(4,6);

            meetingList2.AddMeeting(2,3);
            meetingList2.AddMeeting(3,4);
            meetingList2.AddMeeting(5,6);
            List<Meeting> intersectionsList = FindInterSections(meetingList1, meetingList2);
        }

        private List<Meeting> FindInterSections(MeetingList meetingList1,MeetingList meetingList2)
        {
            meetingList1.list.Sort();
            meetingList2.list.Sort();
            List<Meeting> intersectingList = new List<Meeting>();
            foreach (var item in meetingList1.list)
            {
                foreach (var other in meetingList2.list)
                {
                    if ((item.StartTime >= other.StartTime && item.EndTime <= other.EndTime) ||
                        (other.StartTime >=item.StartTime && other.EndTime <=item.EndTime))
                    {
                        intersectingList.Add(item);
                        intersectingList.Add(other);
                    }
                }
            }
            return intersectingList; 
        }
    }


    public class MeetingList
    {
        public List<Meeting> list;
        public MeetingList()
        {
            list = new List<Meeting>();
        }
        public void AddMeeting(int start, int end)
        {
            list.Add(new Meeting(start,end));
        }
    }

    public class Meeting : IComparable<Meeting>
    {
        public int StartTime { set; get; }
        public int EndTime { set; get; }

        public Meeting(int start, int end)
        {
            StartTime = start;
            EndTime = end;
        }

        public int CompareTo(Meeting other)
        {
            if (StartTime > other.StartTime)
            {
                return 1;
            }
            else if (StartTime < other.StartTime)
            {
                return -1;
            }
            return 0;
        }
    }
}

This is one solution of the problem I have found.

An efficient approach is to first sort the intervals according to starting time. Once we have the sorted intervals, we can combine all intervals in a linear traversal. The idea is, in sorted array of intervals, if interval[i] doesn't overlap with interval[i-1], then interval[i+1] cannot overlap with interval[i-1] because starting time of interval[i+1] must be greater than or equal to interval[i]. Following is the detailed step-by-step algorithm.

Answer 1

You could make the Meeting class generic with the T : IComparable<T> constraint. Thus you'll be able to use any type as a time value:

[DebuggerDisplay("{Start} .. {End}")]
public sealed class Meeting<T>
    where T : IComparable<T>
{
    // You can replace these readonly fields with the auto-properties { get; private set; }:
    public readonly T Start;
    public readonly T End;

    public Meeting(T start, T end)
    {
        Start = start;
        End = end;
    }
}

Next you need a comparer:

public sealed class MeetingComparer<T> : IEqualityComparer<Meeting<T>>
    where T : IComparable<T>
{
    public bool Equals(Meeting<T> x, Meeting<T> y)
    {
        // We can use only 2 sequential comparisons to check for the intersection:
        return x.Start.CompareTo(y.Start) >= 0
            ? x.Start.CompareTo(y.End) <= 0
            : y.Start.CompareTo(x.End) <= 0;
    }

    public int GetHashCode(Meeting<T> obj)
    {
        // Make all meetings have the same hash code.
        // In this case the Equals method will be called for each object.
        return 1;
    }
}

And finally you could use LINQ to find the intersecting meetings:

private static IEnumerable<Meeting<T>> FindIntersections<T>(IEnumerable<Meeting<T>> list1,
    IEnumerable<Meeting<T>> list2)
    where T : IComparable<T>
{
    return list1.Join(list2, p => p, p => p,
        (a, b) => new[] { a, b }, new MeetingComparer<T>())
            .SelectMany(p => p);
}

Sample:

var list1 = new List<Meeting<int>>
                {
                    new Meeting<int>(0, 1),
                    new Meeting<int>(100, 111),
                    new Meeting<int>(20, 41),
                    new Meeting<int>(10, 11)
                };
var list2 = new List<Meeting<int>>
                {
                    new Meeting<int>(2, 3),
                    new Meeting<int>(105, 106),
                    new Meeting<int>(40, 41),
                    new Meeting<int>(15, 16)
                };

var intersection = FindIntersections(list1, list2);

EDIT
Try this code to find intersections of the sorted sets. It has complexity \$O(N+M)\$:

private static IEnumerable<Meeting<T>> FindIntersections<T>(IEnumerable<Meeting<T>> listX,
    IEnumerable<Meeting<T>> listY)
    where T : IComparable<T>
{
    var iteratorX = listX.GetEnumerator();
    var iteratorY = listY.GetEnumerator();
    Meeting<T> lastX = null;
    Meeting<T> lastY = null;
    iteratorX.MoveNext();
    iteratorY.MoveNext();
    while (iteratorX.Current != null && iteratorY.Current != null)
    {
        Meeting<T> x = iteratorX.Current;
        Meeting<T> y = iteratorY.Current;

        // Move iterators if needed:
        if (x.End.CompareTo(y.Start) < 0)
        {
            iteratorX.MoveNext();
            continue;
        }
        if (y.End.CompareTo(x.Start) < 0)
        {
            iteratorY.MoveNext();
            continue;
        }

        // Add items to the resulting set, if the items aren't already there:
        if (lastX != x)
        {
            yield return x;
            lastX = x;
        }
        if (lastY != y)
        {
            yield return y;
            lastY = y;
        }

        // Determine which iterator should be moved first:
        if (y.End.CompareTo(x.End) >= 0)
        {
            iteratorX.MoveNext();
        }
        else
        {
            iteratorY.MoveNext();
        }
    }
}

The method above:

• Returns a set of the unique Meeting<T>s.
• Supports case if one range overlaps several ranges in another set.

Answer 2

Your intersection code only catches cases where a meeting is entirely within the time of another meeting. For example, it will not catch the overlap in 10am-2pm and 1pm-4pm. Instead, its easier to check for non-intersection, and then negate. This is a popular approach to checking for intersection in rectangles.

if (!(item.StartTime > other.endTime || item.endTime < other.StartTime))  {
    // overlap
}

As others have mentioned the algorithmic improvement is to use a merge to get O(M + N) complexity. The tricky part is that you compare the ends of the meeting times to decide which to advance.

Imagine one list with 1 all day meeting and the other with meetings every hour. The first overlaps works just fine, but the all day meeting started first and if you advance that list your search is ended prematurely.

If you advance the list which has the earlier ending meeting you will be fine since that meeting ends before the other list's next item starts, you won't miss any overlaps.

int meet1 = 0;
int meet2 = 0;

while (meet1 < list1.Count && meet2 < list2.Count) {
    if (intersects(list1[meet1], list2[meet2]) {
       // add to list
   }
   if (list1[meet1].endTime < list2[meet2].endTime) {
      ++meet1;
   } else {
      ++meet2; 
   }
}

(feel free to edit and flesh this out)

Answer 3

I would make the MeetingList simpler and take both conditions out of the if for better maintainability:

public class IntersectingMeetings
{
    public static List<Meeting> FindInterSections(MeetingList meetingList1, MeetingList meetingList2)
    {
        meetingList1.Sort();
        meetingList2.Sort();
        List<Meeting> intersectingList = new List<Meeting>();
        foreach (var first in meetingList1)
        {
            foreach (var second in meetingList2)
            {
                bool case1 = (first.StartTime >= second.StartTime && first.EndTime <= second.EndTime);
                bool case2 = (second.StartTime >= first.StartTime && second.EndTime <= first.EndTime);

                if (case1 || case2)
                {
                    intersectingList.Add(first);
                    intersectingList.Add(second);
                }
            }
        }
        return intersectingList;
    }
}


public class MeetingList : List<Meeting>
{
    public void AddMeeting(int start, int end)
    {
        Add(new Meeting(start, end));
    }
}

Answer 4

If you don't count the "sorting of the lists" itself, you can iterate through both lists at the same time in a loop (while, not foreach) and only once which would be O(M+N) or even less: O(M+N) is a maximum, for "good sets" it can go as low as O(M) or O(N) depending on overlaps (thanks for pointing that out in the comments)

It's too late here for a complete code, but here's a rundown with some pseudocode (comparison methods) to show the algorithm I would use... (EDIT2: Updated the comparison and validated it against several overlapping scenarios. The "isBefore" was a bit sketchy - "end is before other end" should do the trick)

I still don't think there is a much faster solution... LINQ might make it more "versatile" but certainly not "more efficient" IMHO - with all that method calling in between...

index1 = 0;
index2 = 0;

// as soon as the first list is exhausted, there can be no more overlaps
while (index1 < list1.Count && index2 < list2.Count)
{
         // check for overlapping timeframe in either direction...
         if (list1[index1].StartTime < list2[index2].EndTime && 
             list1[index1].EndTime > list2[index2].StartTime)
         {
              // overlaps - do whatever...
         }

         // Advance the one list that has the "older" ending time, 
         // doesn't matter whicht if both are equal.
         if (list1[index1].EndTime < list2[index2].EndTime)
              index1++;
         else
              index2++;
}