Insert Interval - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'CURRENT', CURRENT_COLOR = 'blue';
const NEW_COLOR = 'orange', MERGED_COLOR = 'green';

function visMainFunction(inputIntervals, inputNewInterval) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startBatch();
    const intervals = new VisArray(...inputIntervals).options({ labelExtractionPolicy: JSON.stringify });
    const newInterval = new VisArray(...inputNewInterval);
    const result = new VisArray().options({ labelExtractionPolicy: JSON.stringify });
    let index = 0, n = intervals.length;
    makeVisVariable(index).registerAsIndexPointer(intervals, CURRENT);
    endBatch();
    
    // Step 1: Add all intervals before newInterval
    startPartialBatch();
    notification(`
        📌 <b>Step 1: Add all intervals that end before the new interval starts.</b><br>
        An existing interval is considered to <b>end before</b> the new interval if its <b>end</b> value is strictly less than the new interval’s <b>start</b>.<br><br>
        ✅ Because the intervals are <b>sorted</b> and <b>non-overlapping</b>, we can keep adding intervals to the result
        until we encounter one that no longer ends before the new interval — at that point, we know we've already included all such intervals,
        and none of the remaining intervals can qualify.
    `);
    while (index < n && intervals[index][1] < newInterval[0]) {
        notification(`
            ✅ <b>Non-overlapping interval found:</b> This interval <b>ends before</b> the new interval starts, so it does not overlap.<br>
            We can safely add it to the result unchanged.<br><br>
            ${generateIntervalsSvgContent([
                [[...intervals[index], { text: "Current Interval", color: CURRENT_COLOR }]],
                [[...newInterval, { text: "New Interval", color: NEW_COLOR }]]
            ])}
        `);
        result.push(intervals[index]);
        index += 1;
    }
    endBatch();

    // Step 2: Merge overlapping intervals
    startPartialBatch();
    notification(`
        📌 <b>Step 2: Merge all intervals that overlap with the new interval.</b><br>
        From <b>Step 1</b>, we’ve already added every interval that <b>ends before</b> the new interval starts.
        That means the remaining intervals either <b>overlap</b> with it or come <b>after</b> it.<br><br>
        An existing interval is considered to <b>overlap</b> with the new interval if its <b>start</b> value is less than or equal to the new interval’s <b>end</b>.<br><br>
        ✅ Because the intervals are <b>sorted</b> and <b>non-overlapping</b>, any overlapping intervals appear <b>contiguously</b>.
        We keep merging them into the new interval until we reach one whose start is greater than the current merged interval’s end —
        at that point, all overlaps have been handled, and merging is complete.
    `);
    while (index < n && intervals[index][0] <= newInterval[1]) {
        const mergedInterval = [ Math.min(newInterval[0], intervals[index][0]), Math.max(newInterval[1], intervals[index][1])];

        const svgContent = generateIntervalsSvgContent([
            [[...intervals[index], { text: "Existing Interval", color: CURRENT_COLOR }]],
            [[...newInterval, { text: "New Interval", color: NEW_COLOR }]],
            [[...mergedInterval, { text: "Merged Interval", color: MERGED_COLOR }]]
        ]);

        notification(`
             🔄 <b>Overlapping interval detected!</b><br>
            The current interval’s <b>start</b> lies before or within the new interval’s <b>end</b>, so they overlap.<br>
            We merge their ranges to form an updated <b>merged interval</b> and update the <b>new interval</b> itself to represent this expanded range,
            rather than adding the current interval separately to the result.<br><br>
            🔁 We then continue checking the next intervals to see if they also overlap with this newly updated interval.
            ${svgContent}
        `);

        newInterval[0] = mergedInterval[0];
        newInterval[1] = mergedInterval[1];

        index += 1;
    }
    notification(`
        ✅ <b>Merged interval ready for insertion:</b><br>
        All overlapping intervals have been merged into a single <b>updated new interval</b> — this interval now represents the full combined range.<br>
        Since the input intervals are <b>sorted by start time</b>, any remaining intervals must start <b>after</b> this merged one,
        so no further merges are possible.<br><br>
        📦 The <b>updated new interval</b> is now ready to be added to the result.
    `);
    result.push(newInterval);
    endBatch();

    // Step 3: Add remaining intervals
    startPartialBatch();
    notification(`
        📌 <b>Step 3: Add all intervals that come after the merged interval.</b><br>
        We’ve already handled intervals that <b>end before</b> the new interval (Step 1) and those that <b>overlap</b> with it (Step 2).<br><br>
        Any remaining intervals must start <b>after</b> the updated new interval.<br><br>
        ✅ We can safely append them to the result as they are.
    `);
    while (index < n) {
        result.push(intervals[index]);
        index += 1;
    }
    endBatch();

    // Final visualization of the result
    notification(`
        ✅ The final set of <b>non-overlapping, sorted intervals</b> is shown below:<br>
        ${generateIntervalsSvgContent([result])}
    `);

    return result;
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Guide</b><br><br>

        🔵 <span style="color:${CURRENT_COLOR}">Current Interval / Existing Interval</span><br>
        This represents an interval from the original input that we are currently examining.<br><br>

        🟠 <span style="color:${NEW_COLOR}">New Interval</span><br>
        This is the interval we are trying to insert. As we merge overlaps, this interval will expand to cover the full merged range.<br><br>

        🟢 <span style="color:${MERGED_COLOR}">Merged Interval</span><br>
        This shows the combined coverage when the new interval and the current interval overlap.
        After each merge, the new interval is updated to match this merged range.<br><br>

        📌 We’ll use these colors in the timeline diagrams to show which interval we’re comparing, how they overlap, and what the updated merged interval looks like.
    `);
}

function initClassProperties() {
    setClassProperties(CURRENT, {
        backgroundColor: CURRENT_COLOR
    });
}

Approach

We are given a list of existing intervals and one new interval to insert. The goal is to return a new list of intervals that: includes the new interval, stays sorted by start time, and remains non-overlapping.

The key observation that makes this efficient is: the existing intervals are already sorted by start time and are non-overlapping. We take advantage of this structure and process the intervals from left to right in a single pass.

High-Level Strategy

Step 1: Add all intervals that end before the new interval starts.
Any interval whose end is strictly less than the new interval’s start cannot overlap with the new interval. Because the input is sorted and non-overlapping, we can safely copy all of these intervals directly into the result. Once we reach an interval that does not end before the new interval, we know there are no more "completely before" intervals left.
Step 2: Merge all intervals that overlap with the new interval.
Starting from the first interval that did not qualify for Step 1, we now check for overlap with the (possibly growing) new interval. An interval overlaps if its start is less than or equal to the new interval’s end.

When we detect overlap, we merge by expanding the new interval to cover both ranges: the new start becomes min(currentStart, newStart), and the new end becomes max(currentEnd, newEnd).

We repeat this as long as intervals continue to overlap. Because the input is sorted and non-overlapping, all overlapping intervals will appear contiguously. After this merging loop finishes, the "updated new interval" now represents one combined interval that covers everything that touched it. We then push this merged interval into the result.
Step 3: Add all remaining intervals that come after the merged interval.
At this point, we have already: (1) added all intervals that end before the new interval, and (2) merged every interval that overlaps with it. Any remaining intervals must start strictly after the merged interval ends. Since they cannot overlap with it, we can append them directly to the result.

Why This Works

Sorted + non-overlapping input: Because the original intervals never overlap and are sorted by start time, all intervals that are "before" the new interval come first, then any that "touch" it, then all that are "after" it. We never have to look backward.
Single pass: We walk through the intervals from left to right once, updating the new interval as needed. This gives us linear time behavior.
Output stays valid: We only ever push: intervals that are fully before, one merged interval that represents all overlaps, and intervals that are fully after. The final result is still sorted and still non-overlapping.

Complexity

Time Complexity: O(N), where N is the number of input intervals. We scan through the list once.

Space Complexity: O(N) for the output list of intervals. Aside from the result array, we only keep a few variables and reuse the new interval as we merge.

Time Complexity

O(N), where N is the number of input intervals. We scan through the list once.

Space Complexity

O(N), where N is the number of input intervals.
The resulting list can have at most N + 1 intervals — one more than the original list if the new interval does not merge with any existing ones.

Input-1

Insert Interval - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

High-Level Strategy

Why This Works

Complexity

Time Complexity

Space Complexity