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.
Finding overlapping time intervals
c#;datetime;interview questions;complexity;interval
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);EDITTry 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.