Skip to main content
5 of 8
This update isn't relevant to this code itself
Jamal
  • 35.2k
  • 13
  • 134
  • 238

Interview intersecting meeting code

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*logM)\$. 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;
        }
    }
}
Gilad
  • 5.4k
  • 5
  • 38
  • 65