Insert Interval

Problem: Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Approach: First we insert the newInterval to the right position according to it's start time and then we merge these intervals.

Implementation in C#:

        public static int[][] InsertAndMergeInterval(int[][] intervals, int[] newInterval)

        {

            if (intervals == null)

            {

                return null;

            }

            int[][] temp = new int[intervals.Length + 1][];

            bool newIntervalAdded = false;

            int j = 0;

            for (int i = 0; i < intervals.Length; ++i)

            {

                if (!newIntervalAdded && intervals[i][0] > newInterval[0])

                {

                    temp[j++] = newInterval;

                    newIntervalAdded = true;

                }

                temp[j++] = intervals[i];

            }        

            if (!newIntervalAdded)

            {

                temp[j] = newInterval;

            }

            return MergeInterval(temp);

        }

        public static int[][] MergeInterval(int[][]intervals)

        {

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

            result.Add(intervals[0]);

            int resultIndex = 0;

            for (int i = 1; i < intervals.Length; ++i)

            {

                if (result[resultIndex][1] >= intervals[i][0])

                {

                    int[] interval = new int[2];

                    interval[0] = result[resultIndex][0];

                    interval[1] = Math.Max(result[resultIndex][1], intervals[i][1]);

                    result.RemoveAt(resultIndex);

                    result.Add(interval);

                }

                else

                {

                    result.Add(intervals[i]);

                    ++resultIndex;

                }

            }

            return result.ToArray();

        }

Complexity: O(n)