using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

​

​

    public class GetLongestSlot

    {

        public static void Main(string[] args)

        {

            Console.WriteLine("Format is HH:mm::ss");

            var cal = new MyCalendar();

            cal.ProcessMeeting(GetSlot(new TimeSpan(6,30,0), new TimeSpan(12, 30, 0)));

            Console.WriteLine(cal.GetLongestFreeSlot());

​

            cal.ProcessMeeting(GetSlot(new TimeSpan(23, 0, 0), new TimeSpan(23, 30, 0)));

            Console.WriteLine(cal.GetLongestFreeSlot());

​

            cal.ProcessMeeting(GetSlot(new TimeSpan(06, 0, 0), new TimeSpan(13, 0, 0)));

            Console.WriteLine(cal.GetLongestFreeSlot());

​

            cal.ProcessMeeting(GetSlot(new TimeSpan(16, 0, 0), new TimeSpan(18, 0, 0)));

            Console.WriteLine(cal.GetLongestFreeSlot());

​

            cal.ProcessMeeting(GetSlot(new TimeSpan(3, 0, 0), new TimeSpan(6, 0, 0)));

            Console.WriteLine(cal.GetLongestFreeSlot());

​

​

            cal.ProcessMeeting(GetSlot(0, 23));

            Console.WriteLine(cal.GetLongestFreeSlot());

​

        }

​

        public static Slot GetSlot(int startHour, int endHour)

        {

            return new Slot(MyCalendar.GetStartOfDay().AddHours(startHour),

                MyCalendar.GetStartOfDay().AddHours(endHour));

        }

​

        public static Slot GetSlot(TimeSpan startSpan, TimeSpan endSpan)

        {

            return new Slot(MyCalendar.GetStartOfDay().Add(startSpan),

                MyCalendar.GetStartOfDay().Add(endSpan));

        }

    }

​

​

    public class MyCalendar

    {

​

        Node root;

​

        public void ProcessMeeting(Slot meetingSlot)

        {

            Console.WriteLine("Adding "+meetingSlot.start.Hour+":"+meetingSlot.start.Minute+":"+meetingSlot.start.Second +

                              " to " +meetingSlot.end.Hour+":"+meetingSlot.end.Minute+":"+meetingSlot.end.Second);

            if (root == null)

            {

                root = new Node();

                root.value = meetingSlot;

​

                root.LeftLongestFree = new Slot(GetStartOfDay(), meetingSlot.start);

                root.RightLongestFree = new Slot(meetingSlot.end, GetEndOfDay());

                return;

            }

​

            AddMeeting(root, meetingSlot, GetStartOfDay(), GetEndOfDay());

​

​

        }

​

        private Node CreateNode(Slot meetingSlot, DateTime leftMost, DateTime rightMost)

        {

            Node node = new Node();

            node.value = meetingSlot;

​

            node.LeftLongestFree = new Slot(leftMost, meetingSlot.start);

            node.RightLongestFree = new Slot(meetingSlot.end, rightMost);

            return node;

        }

​

        private void AddMeeting(

            Node node,

            Slot meetingSlot,

            DateTime leftMost,

            DateTime rightMost)

        {

            // entirely on left

            if (node.value.start >= meetingSlot.end)

            {

                if (node.left != null)

                {

                    AddMeeting(node.left, meetingSlot, leftMost, node.value.start);

                }

                else

                {

                    node.left = CreateNode(meetingSlot, leftMost, node.value.start);

                }

​

                // update all the parents

                node.LeftLongestFree = node.left.GetLongestFree();

            }

            else if (node.value.end <= meetingSlot.start)

            {

                if (node.right != null)

                {

                    AddMeeting(node.right, meetingSlot, node.value.end, rightMost);

                }

                else

                {

                    node.right = CreateNode(meetingSlot, node.value.end, rightMost);

                }

                node.RightLongestFree = node.right.GetLongestFree();

            }

            else

            {

                Slot splitMeeting;

                if (meetingSlot.start < node.value.start)

                {

                    splitMeeting = new Slot(meetingSlot.start, node.value.start);

                    AddMeeting(node, splitMeeting, leftMost, rightMost );

                }

                if ( meetingSlot.end > node.value.end)

                {

                    splitMeeting = new Slot(node.value.end, meetingSlot.end);

                    AddMeeting(node, splitMeeting, leftMost, rightMost);

                }

            }

        }

​

        public Slot GetLongestFreeSlot()

        {

            if (root == null)

            {

                // last tick of the day

                return new Slot(GetStartOfDay(), GetEndOfDay());

            }

​

            return root.GetLongestFree();

        }

​

        public static DateTime GetStartOfDay()

        {

            return new DateTime(2019, 01, 10);

        }

​

        public static DateTime GetEndOfDay()

        {

            return new DateTime(2019, 01, 10).AddDays(1).AddTicks(-1);

        }

    }

​

​

    public class Node

    {

        public Slot value;

        public Node left;

        public Node right;

        public Slot LeftLongestFree;

        public Slot RightLongestFree;

​

        public Slot GetLongestFree()

        {

            if (LeftLongestFree.GetLength() > RightLongestFree.GetLength())

            {

                return LeftLongestFree;

            }

            return RightLongestFree;

        }

    }

​

​

    public class Slot

    {

​

        public DateTime start;

        public DateTime end;

​

        public TimeSpan GetLength()

        {

            return end - start;

        }

​

        public Slot(DateTime start, DateTime end)

        {

            // TODO: add validation that start is <=end

            this.start = start;

            this.end = end;

        }

​

        public override string ToString()

        {

            return "\t LongestInterval start:"+start.Hour+":"+start.Minute+":"+start.Second+

                   " end:"+end.Hour+":"+end.Minute+":"+end.Second +

                   ", length "+GetLength();

        }

    }

​