10
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ If I understand you correctly and both lists are sorted - finding intersection would be equivalent to merging these two sorted lists and can be done with complexity of O(m+n) \$\endgroup\$
    – sha
    Dec 6, 2014 at 23:32
  • \$\begingroup\$ This is not quite Merge sort, since there is no equality here, you need to test for intersection which can be in 4 different use cases. \$\endgroup\$
    – Gilad
    Dec 6, 2014 at 23:33
  • 1
    \$\begingroup\$ Still, if they are sorted - I'm pretty sure you can get away with m+n. I will try to write it a bit later. \$\endgroup\$
    – sha
    Dec 6, 2014 at 23:35
  • \$\begingroup\$ This is marked "interview-questions". In the interview, did they give you any indication that time complexity was an evaluation criteria, or that there would be very large numbers of meetings involved? \$\endgroup\$ Dec 10, 2014 at 18:08
  • \$\begingroup\$ @BenAaronson it wasn't my Interview, but I think that time complexity is always an issue. \$\endgroup\$
    – Gilad
    Dec 10, 2014 at 18:15

4 Answers 4

8
\$\begingroup\$

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.
\$\endgroup\$
7
\$\begingroup\$

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)

\$\endgroup\$
1
  • \$\begingroup\$ @RyanHeitner fixed \$\endgroup\$ Dec 14, 2018 at 5:10
5
\$\begingroup\$

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));
    }
}
\$\endgroup\$
5
\$\begingroup\$

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++;
}
\$\endgroup\$
4
  • \$\begingroup\$ It actually will be O(min(m,n)) :) \$\endgroup\$
    – sha
    Dec 7, 2014 at 0:36
  • 1
    \$\begingroup\$ @sha Only one of index1 or index2 is incremented so in the worst case one list reaches the end and the other is just shy of its end. O(M + N). \$\endgroup\$ Dec 7, 2014 at 3:59
  • \$\begingroup\$ isBefore will miss some intersections. list1=[(2,3),(4,5)] list2=[(1,5)] would fail to find the overlap between (4,5) and (1,5). \$\endgroup\$ Dec 7, 2014 at 6:21
  • \$\begingroup\$ Interesting... I shall have to look into a more precise definition of that. I'm still certain it can be done by only going through the sorted lists once, as I did that before. \$\endgroup\$ Dec 10, 2014 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.