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.