using System;

using System.Collections.Generic;

public class BinaryTreeNode<D>

{

    public D Data { get; set; }

    public BinaryTreeNode<D> Left { get; set; }

    public BinaryTreeNode<D> Right { get; set; }

}

​

public class BSTNode<K,D> : BinaryTreeNode<D> where K : IComparable

{

    public BSTNode() {}

    public BSTNode(K key, D data) { this.Key = key; this.Data = data; }

    public K Key { get; set; }

    public virtual void Insert(K key, D data)

    {

        throw new NotImplementedException();    

    }

    public void Insert(BSTNode<K,D> node)

    {

        if(node.Key.CompareTo(this.Key)<=0)

        {

            if(node.Left==null) { node.Left = node; }

            else

            {

                (node.Left as BSTNode<K,D>).Insert(node);

            }

        }

        else

        {

            if(node.Right==null) { node.Right = node; }

            else

            {

                (node.Right as BSTNode<K,D>).Insert(node);

            }

        }

    }

}

​

public class BST<K,D> where K : IComparable

{

    public BSTNode<K,D> Root { get; set; }

    public void Insert(K key, D data)

    {

        if(Root==null) { this.Root = new BSTNode<K,D>(key,data); }

        else

        {

            this.Root.Insert(key, data);

        }

    }

    public void Insert(BSTNode<K,D> node)

    {

        if(Root==null) { this.Root = node; }

        else

        {

            this.Root.Insert(node);

        }

    }

}

​

public interface IInterval<T> where T:IComparable

{

    T Low { get; }

    T High { get; }

}

​

public class IntervalComparer<T> : IComparer<IInterval<T>> where T:IComparable

{

    public int Compare(IInterval<T> x, IInterval<T> y)

    {

        return x.Low.CompareTo()pareTo(y.Low);

    }

}

​

public class Age : IInterval<DateTime>

{

    public Age(DateTime birth, DateTime death) { Birth = birth; Death = death; }

    public DateTime Birth { get; set; }

    public DateTime Death { get; set; } 

    public DateTime Low { get { return this.Birth; } }

    public DateTime High { get { return this.Death; } }

}

​

public class IntervalNode<T> : BSTNode<T,IInterval<T>> where T : IComparable

{

    public IntervalNode(IInterval<T> interval) : base(interval.Low, interval) 

    { 

        this.Max = interval.Low; 

        this.Interval = interval; 

    }   

    public IntervalNode(T center){ this.Center = center; }

    public IInterval<T> Interval { get; private set; }

    public T Max { get; private set; }      

    public T Center {get; private set; }

    public List<IInterval<T>> OverlapSortedByLow { get; set; }

    public List<IInterval<T>> OverlapSortedByHigh { get; set; }

    public void Insert(IInterval<T> interval)

    {

        var i = new IntervalNode<T>(interval);

        base.Insert(i);

    }

    public void Insert(List<IInterval<T>> intervals)

    {

        var toLeft = new List<IInterval<T>>();

        var toRight = new List<IInterval<T>>();

        var overlapByLow = new List<IInterval<T>>();

        var overlapByHigh = new List<IInterval<T>>();

        foreach(var i in intervals)

        {

            if(i.Low.CompareTo(this.Center)<0 && i.High.CompareTo(this.Center)<0)

            {

                toLeft.Add(i);

            }

            else if(i.Low.CompareTo(this.Center)>0 && i.High.CompareTo(this.Center)>0)

            {

                toRight.Add(i);

            }

        }

    }

}

​

public class IntervalTree<K> : BST<K,IInterval<K>> where K : IComparable

{

    public IntervalTree(List<IInterval<K>> intervals, Func<K,K,K> calcCenter)

    {

        intervals.Sort(new IntervalComparer<K>());

        K min=default(K), max=default(K);

        foreach(var k in intervals)

        {

            if(min.CompareTo(default(K))==0 || k.Low.CompareTo(min)<0)

            {

                min = k.Low;

            }

​

            if(max.CompareTo(default(K))==0 || k.High.CompareTo(max)>0)

            {

                max = k.High;

            }           

        }

        var center = calcCenter(min,max);

        var root = new IntervalNode<K>(center);

        root.Insert(intervals);

    }

    public void Insert(IInterval<K> interval)

    {

        var i = new IntervalNode<K>(interval);

        base.Insert(i);

    }

    public IInterval<K> Overlap(IInterval<K> interval)

    {

        if(this.Root==null) { return null; }

        var current = this.Root as IntervalNode<K>;

        while(current!=null && !Overlap(current.Interval,interval))

        {

            if(current.Left!=null &&

                interval.Low.CompareTo((current.Left as IntervalNode<K>).Max)<=0)

            {

                current = current.Left as IntervalNode<K>;

            }

            else

            {

                current = current.Right as IntervalNode<K>;

            }

        }       

        return current!=null?current.Interval:null;

    }

    public List<IInterval<K>> OverlapIntervals(IInterval<K> interval)

    {

        throw new NotImplementedException();

    }

    private bool Overlap(IInterval<K> int1, IInterval<K> int2)

    {

        return (int1.Low.CompareTo(int2.High)<=0 && int2.Low.CompareTo(int1.High)<=0);

    }

}

​

​

public class Solution

{

    public DateTime GetHighestPopulationYear(List<Age> ages)

    {

        var intervalTree = new IntervalTree<DateTime>();

        DateTime min = DateTime.MaxValue;

        DateTime max = DateTime.MinValue;

        foreach(var a in ages)

        {

            intervalTree.Insert(a);

            if(a.Birth < min)

            {

                min = a.Birth;

            }

            if(a.Death > max)

            {

                max = a.Death;

            }

        }

        int maxCount = int.MinValue;

        DateTime maxYear = DateTime.MinValue;

        for(var current = min; current <= max; current = current.AddYears(1))

        {

            var i = new Age(current,current);

            var count = intervalTree.OverlapIntervals(i).Count;

            if(count>maxCount)

            {

                maxCount = count;

                maxYear = current;

            }

        }

        return maxYear;

    }

}

public class Program

{

    public static void Main()

    {

        example();

    }

    private static void example()   

    {

        var ages = new List<Age>()

        {

            new Age(new DateTime(1929,21,10), new DateTime(1950,1,21)),

            new Age(new DateTime(1952,9,3), new DateTime(1977,6,7)),

            new Age(new DateTime(1931,8,8), new DateTime(1946,23,9)),

            new Age(new DateTime(1940,2,3), new DateTime(1958,12,18))               

        };

    }

}