Insert Interval

Insert a new interval into a sorted, non-overlapping list in one pass: copy what ends before it, merge what overlaps it, copy the rest.

The idea

Because the list is sorted and has no overlaps, it falls into three runs relative to the new interval: intervals that end before it starts, intervals that overlap it, and intervals that start after it ends. Copy the first run, fold the middle run into the new interval by taking the smallest start and largest end, add the result once, then copy the last run.

Code

public static int[][] Insert(int[][] intervals, int[] newInterval) {
    var res = new List<int[]>();
    int i = 0, n = intervals.Length;
    while (i < n && intervals[i][1] < newInterval[0])
        res.Add(intervals[i++]); // ends before the new one starts
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.Min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.Max(newInterval[1], intervals[i][1]);
        i++;
    }
    res.Add(newInterval);
    while (i < n) res.Add(intervals[i++]); // starts after the merged one ends
    return res.ToArray();
}

Tips

• No sort is needed: the input is already sorted, so this is O(n), unlike Merge Intervals which pays O(n log n) to sort.
• The overlap test in the middle loop only checks start <= newEnd: everything that ended before newStart was already copied by the first loop.
• Touching counts as overlapping here ([1, 5] and [5, 7] become [1, 7]), which is why the first loop uses < and the second <=.

In the .NET library

List<int[]> plus ToArray() is the usual way to build a jagged result of unknown length. The input array newInterval is reused in place; copy it first if the caller still needs the original.