Question

How to add a new interval into a sorted list of non‑overlapping intervals in C#

Answer 1

using System;
using System.Collections.Generic;

class InsertIntervalProgram
{
    public static List<int[]> InsertInterval(List<int[]> intervals, int[] newInterval)
    {
        List<int[]> result = new List<int[]>();
        int i = 0;
        int n = intervals.Count;

        // 1. Add all intervals that end BEFORE the new interval starts.
        // These cannot overlap.
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.Add(intervals[i]);
            i++;
        }

        // 2. Merge all intervals that DO overlap with the new interval.
        // Overlap condition: intervals[i].start <= newInterval.end
        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++;
        }

        // Add the merged interval
        result.Add(newInterval);

        // 3. Add all remaining intervals (those starting AFTER new interval ends)
        while (i < n)
        {
            result.Add(intervals[i]);
            i++;
        }

        return result;
    }

    static void Main()
    {
        List<int[]> intervals = new List<int[]>
        {
            new int[] {1, 3},
            new int[] {6, 8},
            new int[] {13, 18}
        };

        int[] newInterval1 = {9, 11};
        var updated = InsertInterval(intervals, newInterval1);

        int[] newInterval2 = {2, 5};
        updated = InsertInterval(updated, newInterval2);

        Console.WriteLine("Updated intervals:");
        foreach (var iv in updated) {
            Console.Write("[" + iv[0] + "," + iv[1] + "] ");
        }
    }
}


/*
run:

Updated intervals:
[1,5] [6,8] [9,11] [13,18] 

*/

 

70+ SQL courses for beginners and professionals