using System;

using System.Collections.Generic;

using System.Collections;

public class Program

{

    //https://www.programcreek.com/2012/12/leetcode-insert-interval/

    /*

    Given a set of non-overlapping & sorted intervals, 

    insert a new interval into the intervals (merge if necessary).

    Example 1:

    Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

    Example 2:

    Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

    This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

​

    */

    public static void Main()

    {

        Console.WriteLine("Hello World");

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

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

        example1.Add(new Interval(6,9));

        List<Interval> result = insertNewInterval(example1, new Interval(2,5));

        print(result);

        Console.WriteLine();

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

        example2.Add(new Interval(1,2));

        example2.Add(new Interval(3,5));    

        example2.Add(new Interval(6,7));

        example2.Add(new Interval(8,10));

        example2.Add(new Interval(12,16));

        List<Interval> result2 = insertNewInterval(example2, new Interval(4,9));

        print(result2);

    }

    public class Interval{

        public int start;

        public int end;

        public Interval(int start, int end){

            this.start = start;

            this.end = end;

        }

    }

    public static List<Interval> insertNewInterval(List<Interval> list, Interval newInterval){

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

        foreach(Interval existingInterval in list){

            if(newInterval.start > existingInterval.end){

                result.Add(existingInterval);   

            }else if(newInterval.end < existingInterval.start){

​

                result.Add(newInterval);

                newInterval = existingInterval;

            }else if (newInterval.start <= existingInterval.end || newInterval.end >= existingInterval.start){

                int start = Math.Min(existingInterval.start, newInterval.start);

                int end = Math.Max(newInterval.end, existingInterval.end);

                newInterval = new Interval(start, end);

            }

        }

        result.Add(newInterval);

        return result;

    }

    public static void print(List<Interval> list){

        foreach(Interval i in list){

            String intervalString = String.Format("[{0},{1}]", i.start, i.end);

            Console.Write(intervalString + " " );   

        }   

    }   

}

​

​