Question

How to add a new interval into a sorted array of non‑overlapping intervals in TypeScript

Answer 1

type Interval = [number, number];

function insertInterval(intervals: Interval[], newInterval: Interval): Interval[] {
    const result: Interval[] = [];
    let i: number = 0;
    const n: number = intervals.length;

    // 1. Add all intervals that end BEFORE the new interval starts.
    // These cannot overlap.
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push(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 = [
            Math.min(newInterval[0], intervals[i][0]),
            Math.max(newInterval[1], intervals[i][1])
        ];
        i++;
    }

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

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

    return result;
}

// Usage:
let intervals: Interval[] = [
    [1, 3],
    [6, 8],
    [13, 18]
];

let newInterval1: Interval = [9, 11];
let updated = insertInterval(intervals, newInterval1);

let newInterval2: Interval = [2, 5];
updated = insertInterval(updated, newInterval2);

console.log("Updated intervals:");
let s: string = "";
for (const iv of updated) {
    s += `[${iv[0]},${iv[1]}] `;
}

console.log(s)



/*
run:

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

*/

 

70+ SQL courses for beginners and professionals