using System;

using System.Linq;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        int[] intervals = {1,3};//,{2,6},{8,10},{15,18}};

        List<int[]> list = new List<int[]>();

        list.Add(new int[]{1,3});

        list.Add(new int[]{2,6});

        list.Add(new int[]{8,10});

        list.Add(new int[]{15,18});

        int[] toInsert = {3,4};

        var mergedInterval = InsertIntervals(list.ToArray(),toInsert);

        foreach(var item in mergedInterval){

            Console.WriteLine("{2}{0} {1}{3}",item[0],item[1],"{","}");

        }

    }

    public static int[][] InsertIntervals(int[][] intervals,int[] toInsert){

        var ix = intervals.ToList();

        ix.Add(toInsert);

        ix.ToArray();

        int[][] sortedInterval = ix.OrderBy(interval=>interval[0]).ToArray();

        List<int[]> mergedList = new List<int[]>();

        Console.WriteLine("{0}, {1}",intervals.First()[0],intervals.First()[1]);

        foreach(int[] interval in sortedInterval){

            if(mergedList.Count == 0 || mergedList.Last()[1] < interval[0]){

                mergedList.Add(interval);

            }else{

                mergedList.Last()[1] = Math.Max(mergedList.Last()[1],interval[1]);

            }

        }

        return mergedList.ToArray();

    }

}