using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    private static List<Interval> insert(List<Interval> input, Interval newInterval) {

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

        int indexToInsert = -1;

        for(int index = 0; index < (input.Count); index++) {            

            if (newInterval.start > input[index].end) {

                indexToInsert = index + 1;

            }

            else {

                indexToInsert = (index - 1 > 0) ? (index -1) : 0;

            }

        }

        for (int index =0; index < input.Count; index++) {

            if (index < indexToInsert) {

                merged.Add(input[index]);

                continue;

            }

            else if (index == indexToInsert) {

                Interval a,b = null;

                if (newInterval.start < input[index].start) {

                    a = newInterval;

                    b = input[index];

                } else {

                    a = input[index];

                    b = newInterval;

                }

                if (b.start <= a.end) {

                    if (b.end < a.end) {

                        merged.Add(new Interval(a.start, a.end));

                    }

                    else {

                        merged.Add(new Interval(a.start, b.end));

                    }

                }               

            } else {

                Interval lastMerged = merged.Last();

                Interval current = input[index];

                if (current.start <= lastMerged.end) {

                    if (current.end > lastMerged.end) {

                        lastMerged.end = current.end;

                    }

                } else {

                    merged.Add(current);

                }

            }           

        }

​

        return merged;

    }

    public static void Main()

    {

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

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

        input.Add(new Interval(5, 7));

        input.Add(new Interval(8, 12));

        Console.Write("Intervals after inserting the new interval: ");

        foreach (Interval interval in insert(input, new Interval(4, 6)))

            Console.Write("[" + interval.start + "," + interval.end + "] ");

        Console.WriteLine();

​

        input = new List<Interval>();

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

        input.Add(new Interval(5, 7));

        input.Add(new Interval(8, 12));

        Console.Write("Intervals after inserting the new interval: ");

        foreach (Interval interval in insert(input, new Interval(4, 10)))

            Console.Write("[" + interval.start + "," + interval.end + "] ");

        Console.WriteLine();

​

        input = new List<Interval>();

        input.Add(new Interval(2, 3));

        input.Add(new Interval(5, 7));

        Console.Write("Intervals after inserting the new interval: ");

        foreach (Interval interval in insert(input, new Interval(1, 4)))

            Console.Write("[" + interval.start + "," + interval.end + "] ");

        Console.WriteLine();

    }

}

​

public class Interval {

  public int start;

  public int end;

​

  public Interval(int start, int end) {

    this.start = start;

    this.end = end;

  }

};