public class IntervalsIntersection
{
    /// <summary>
    /// O(m + n)
    /// </summary>
    /// <param name="arr1"></param>
    /// <param name="arr2"></param>
    /// <returns></returns>
    public List<Interval> merge(Interval[] arr1, Interval[] arr2)
    {
        List<Interval> result = new List<Interval>();
        int i1 = 0, i2 = 0;
        while (i1 < arr1.Length && i2 < arr2.Length)
        {
            if (DoesIntersect(arr1[i1], arr2[i2]))
            {
                result.Add(FindIntersection(arr1[i1], arr2[i2]));
                if (IsSubInterval(arr1[i1], arr2[i2]))
                {
                    i2++;
                }
                else if (IsSubInterval(arr2[i2], arr1[i1]))
                {
                    i1++;
                }
                else
                {
                    i1++;
                    i2++;
                }
            }
            else
            {
                if (arr1[i1].Start < arr2[i2].Start)
                {
                    i1++;
                }
                else
                {
                    i2++;
                }
            }
        }
        return result;
    }

    public bool IsSubInterval(Interval interval, Interval subInterval)
    {
        if (subInterval.Start >= interval.Start && subInterval.End <= interval.End)
        {
            return true;
        }
        return false;
    }

    public bool DoesIntersect(Interval interval1, Interval interval2)
    {
        if (interval2.Start >= interval1.Start && interval2.Start <= interval1.End 
            || interval1.Start >= interval2.Start && interval1.Start <= interval2.End)
        {
            return true;
        }
        return false;
    }

    public Interval FindIntersection(Interval i1, Interval i2)
    {
        return new Interval(Math.Max(i1.Start, i2.Start), Math.Min(i1.End, i2.End));
    }
}