using System;

using System.Collections.Generic;

​

public class Interval

{

    public int start;

    public int end;

    public Interval(int s, int e)

    {

        start = s;

        end = e;

    }

}

​

public class Program

{

    public List<Interval> FindAllOverlappingInterval(List<Interval> A, List<Interval> B)

    {

        List<Interval> result = new List<Interval>();

        int i = 0, j = 0;

        while(i < A.Count && j < B.Count)

        {

            //Console.WriteLine("A.start = {0}, A.end = {1}", A[i].start, A[i].end);

            //Console.WriteLine("B.start = {0}, B.end = {1}", B[j].start, B[j].end);

            if(A[i].start <= B[j].start && A[i].end <= B[j].start)

            {

                i++;

            }

            else if(B[j].start <= A[i].start && B[j].end <= A[i].start)

            {

                j++;

            }

            else if((A[i].start >= B[j].start && A[i].start < B[j].end)||(B[j].start >= A[i].start && B[j].start < A[i].end))

            {

                int start = Math.Max(A[i].start, B[j].start);

                int end = Math.Min(A[i].end, B[j].end);

                result.Add(new Interval(start,end));

                if(A[i].end <= B[i].end) //Move the one whose interval has ended

                    i++;

                else

                    j++;                

            }

        }

        return result;

    }

    public static void Main()

    {

        Console.WriteLine("Hello World o");

        List<Interval> A = new List<Interval>();    

        List<Interval> B = new List<Interval>();

        A.Add(new Interval(1,35));

        //A.Add(new Interval(4,6));

        //A.Add(new Interval(8,12));

        //A.Add(new Interval(20,50));

        B.Add(new Interval(1,3));

        B.Add(new Interval(4,5));

        B.Add(new Interval(9,14));

        B.Add(new Interval(18,20));

        B.Add(new Interval(21,24));

        B.Add(new Interval(25,31));

        Program myObj = new Program();

        List<Interval> result = myObj.FindAllOverlappingInterval(A,B);

        myObj.Display(result);

    }

    private void Display(List<Interval> A)

    {

        Console.WriteLine("Overlapping intervals are");

        foreach(Interval interval in A)

        {

            Console.Write("{0} {1}",interval.start, interval.end);

            Console.WriteLine();

        }

    }

}

​