Finding overlapping time intervals 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&lt;Meeting&gt; intersectionsList = FindInterSections(meetingList1, meetingList2);
        }

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


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

    public class Meeting : IComparable&lt;Meeting&gt;
    {
        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 &gt; other.StartTime)
            {
                return 1;
            }
            else if (StartTime &lt; 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.
You could make the Meeting class generic with the T : IComparable&lt;T&gt; constraint. Thus you'll be able to use any type as a time value:

[DebuggerDisplay("{Start} .. {End}")]
public sealed class Meeting&lt;T&gt;
    where T : IComparable&lt;T&gt;
{
    // 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&lt;T&gt; : IEqualityComparer&lt;Meeting&lt;T&gt;&gt;
    where T : IComparable&lt;T&gt;
{
    public bool Equals(Meeting&lt;T&gt; x, Meeting&lt;T&gt; y)
    {
        // We can use only 2 sequential comparisons to check for the intersection:
        return x.Start.CompareTo(y.Start) &gt;= 0
            ? x.Start.CompareTo(y.End) &lt;= 0
            : y.Start.CompareTo(x.End) &lt;= 0;
    }

    public int GetHashCode(Meeting&lt;T&gt; 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&lt;Meeting&lt;T&gt;&gt; FindIntersections&lt;T&gt;(IEnumerable&lt;Meeting&lt;T&gt;&gt; list1,
    IEnumerable&lt;Meeting&lt;T&gt;&gt; list2)
    where T : IComparable&lt;T&gt;
{
    return list1.Join(list2, p =&gt; p, p =&gt; p,
        (a, b) =&gt; new[] { a, b }, new MeetingComparer&lt;T&gt;())
            .SelectMany(p =&gt; p);
}


Sample:

var list1 = new List&lt;Meeting&lt;int&gt;&gt;
                {
                    new Meeting&lt;int&gt;(0, 1),
                    new Meeting&lt;int&gt;(100, 111),
                    new Meeting&lt;int&gt;(20, 41),
                    new Meeting&lt;int&gt;(10, 11)
                };
var list2 = new List&lt;Meeting&lt;int&gt;&gt;
                {
                    new Meeting&lt;int&gt;(2, 3),
                    new Meeting&lt;int&gt;(105, 106),
                    new Meeting&lt;int&gt;(40, 41),
                    new Meeting&lt;int&gt;(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&lt;Meeting&lt;T&gt;&gt; FindIntersections&lt;T&gt;(IEnumerable&lt;Meeting&lt;T&gt;&gt; listX,
    IEnumerable&lt;Meeting&lt;T&gt;&gt; listY)
    where T : IComparable&lt;T&gt;
{
    var iteratorX = listX.GetEnumerator();
    var iteratorY = listY.GetEnumerator();
    Meeting&lt;T&gt; lastX = null;
    Meeting&lt;T&gt; lastY = null;
    iteratorX.MoveNext();
    iteratorY.MoveNext();
    while (iteratorX.Current != null &amp;&amp; iteratorY.Current != null)
    {
        Meeting&lt;T&gt; x = iteratorX.Current;
        Meeting&lt;T&gt; y = iteratorY.Current;

        // Move iterators if needed:
        if (x.End.CompareTo(y.Start) &lt; 0)
        {
            iteratorX.MoveNext();
            continue;
        }
        if (y.End.CompareTo(x.Start) &lt; 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) &gt;= 0)
        {
            iteratorX.MoveNext();
        }
        else
        {
            iteratorY.MoveNext();
        }
    }
}


The method above:


Returns a set of the unique Meeting&lt;T&gt;s.
Supports case if one range overlaps several ranges in another set.