Merge Intervals - 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 LAST_INSERTED_COLOR = 'orange', UPDATED_COLOR = 'green';

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

    startPartialBatch();
    
    const intervals = new VisArray(...inputIntervals).options({ labelExtractionPolicy: JSON.stringify });
    notification(`
        📌 <b>Step 1: Sort all intervals by their start time.</b><br>
        Sorting lets us process intervals in the order they begin (e.g., A → B → C).<br>
        At each step, we only need to compare the
        ${makeColoredSpan('current interval', CURRENT_COLOR)} to the
        ${makeColoredSpan('last inserted interval', LAST_INSERTED_COLOR)} in the result.<br><br>
        If they overlap, we merge by expanding the last inserted interval’s end. This also covers cases like:
        <ul>
            <li>Chain overlaps: A overlaps B, B overlaps C — all three get merged together.</li>
            <li>Shared overlaps: A overlaps both B and C, even if B and C don’t overlap each other — they still merge into one range through A.</li>
        </ul>
        Because we keep the ${makeColoredSpan('last inserted interval', LAST_INSERTED_COLOR)} updated as we go,
        a single left-to-right pass is enough to merge all overlapping intervals.
    `);

    startBatch();
    intervals.sort((a, b) => a[0] - b[0]);
    endBatch();

    notification(`
        ✅ Intervals are now sorted by start time.<br>
        We can begin merging from left to right.
    `);
    endBatch();
    
    startPartialBatch();
    const finalIntervals = new VisArray2D(VisArray.from(intervals[0])); // Start with the first interval
    let index = 1;
    makeVisVariable(index).registerAsIndexPointer(intervals, CURRENT);
    notification(`
        ✅ <b>Step 2: Initialize the merge process.</b><br>
        We begin by placing the first interval ${JSON.stringify(intervals[0])} into the final list — 
        this serves as the ${makeColoredSpan('last inserted interval', LAST_INSERTED_COLOR)}.<br><br>
        Next, we start checking from the <b>second interval onward</b> 
        (${makeColoredSpan('current interval', CURRENT_COLOR)}) to see whether it overlaps with the 
        ${makeColoredSpan('last inserted interval', LAST_INSERTED_COLOR)} or should start a new merged block.
    `);
    endBatch();

    while (index < intervals.length) {
        startPartialBatch();
        
        const lastInsertedInterval = finalIntervals[finalIntervals.length - 1];
        const currentInterval = intervals[index];

        notification(`
            🔍 <b>Compare the ${makeColoredSpan('current interval', CURRENT_COLOR)}</b> 
            ${JSON.stringify(currentInterval)}<br>
            with the ${makeColoredSpan('last inserted interval', LAST_INSERTED_COLOR)} 
            ${JSON.stringify(lastInsertedInterval)}.<br><br>
            We now check if they overlap.
        `);

        if (currentInterval[0] <= lastInsertedInterval[1]) {
            const svgContent = generateIntervalsComparisionContent(lastInsertedInterval, currentInterval, true);

            notification(`
                🔄 <b>Overlap detected!</b><br>
                The ${makeColoredSpan('current interval', CURRENT_COLOR)} starts before or at the end of the 
                ${makeColoredSpan('last inserted interval', LAST_INSERTED_COLOR)}, so they overlap.<br><br>
                Because intervals are <b>sorted by start time</b>, the start of the 
                ${makeColoredSpan('last inserted interval', LAST_INSERTED_COLOR)} is already the smallest possible.<br>
                Therefore, we only need to <b>extend its end</b> to cover the ${makeColoredSpan('current interval', CURRENT_COLOR)}.<br><br>
                ${svgContent}
            `);
            
            lastInsertedInterval[1] = Math.max(lastInsertedInterval[1], currentInterval[1]);
        } else {
            const svgContent = generateIntervalsComparisionContent(lastInsertedInterval, currentInterval);

            notification(`
                ✅ <b>No overlap detected.</b><br>
                The ${makeColoredSpan('current interval', CURRENT_COLOR)} starts after the 
                ${makeColoredSpan('last inserted interval', LAST_INSERTED_COLOR)} ends, so they are disjoint.<br><br>
                We keep them separate by appending ${JSON.stringify(currentInterval)} as a new block in ${makeColoredSpan('finalIntervals', LAST_INSERTED_COLOR)}.<br><br>
                ${svgContent}
            `);
            finalIntervals.push(VisArray.from(currentInterval));
        }

        index += 1;
        endBatch();
    }

    notification(`
        🏁 <b>Final result:</b> The updated set of merged intervals. <br>
        ${generateIntervalsSvgContent([finalIntervals])}
    `);

    return finalIntervals;
}

function generateIntervalsComparisionContent(lastInsertedInterval, currentInterval, renderMergedInterval = false) {
    const mergedIntervalRow = renderMergedInterval 
        ? [[lastInsertedInterval[0], Math.max(lastInsertedInterval[1], currentInterval[1]), { text: "Updated Last Inserted Interval", color: UPDATED_COLOR }]]
        : [];
  
    const svgContent = generateIntervalsSvgContent([
        [[...lastInsertedInterval, { text: "Last Inserted Interval", color: LAST_INSERTED_COLOR }]],
        [[...currentInterval, { text: "Current Interval", color: CURRENT_COLOR }]],
        mergedIntervalRow
    ]);

    return svgContent;
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Guide for Visualization:</b><br>
        To make each step easier to follow, different colors represent specific roles in the algorithm:<br><br>

        🔹 ${makeColoredSpan('<b>Current Interval</b>', CURRENT_COLOR)} <br>
        The interval we are currently processing in the sorted list. It’s being compared against the last inserted interval to determine whether they overlap.<br><br>

        🟧 ${makeColoredSpan('<b>Last Inserted Interval</b>', LAST_INSERTED_COLOR)} <br>
        The most recently added interval in <code>finalIntervals</code>. If the current interval overlaps with it, this interval’s <b>end</b> will be extended to merge them.<br><br>

        🟩 ${makeColoredSpan('<b>Updated Last Inserted Interval</b>', UPDATED_COLOR)} <br>
        The new, expanded interval after merging the overlapping ranges. It replaces the previous orange one in <code>finalIntervals</code>.<br><br>
    `);
}

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

Approach

We are given a list of intervals, and some of them may overlap. The goal is to merge all overlapping intervals and return a new list where no intervals overlap, while still covering exactly the same ranges.

The key idea is: after sorting the intervals by their start time, we only ever need to compare the current interval — the interval we are currently processing — with the last interval inserted into the result — the most recent interval already added to our merged output.

If they overlap, we merge them by expanding that last interval’s end; otherwise, we start a new interval in the result.

This works for both chains of overlaps (A overlaps B, B overlaps C) and shared overlaps (A overlaps both B and C even if B and C don’t overlap each other), when the intervals are in start-time order A → B → C. Because we keep the merged range updated as we go, a single left-to-right pass is enough to merge all overlapping intervals.

High-Level Strategy

Step 1: Sort the intervals by start time.
We first sort all intervals in ascending order of their start value. After sorting, any intervals that overlap will appear next to each other. This makes it possible to merge them in a single linear sweep.
Step 2: Build the merged result from left to right.
We create an array called finalIntervals and put the first interval into it. That interval becomes the last inserted interval — the one we compare against as we process the rest.

As we move through the remaining intervals one by one, each becomes the current interval for comparison:
- If the current interval overlaps with the last inserted interval:
  Two intervals overlap if the current interval’s start is less than or equal to the last inserted interval’s end. In that case, we merge them by extending the end of the last inserted interval to cover both ranges.
  
  We only update the end of the last inserted interval. We do not need to change its start, because the list is already sorted by start time. This ensures that the current interval never starts before the last inserted interval.
- If the current interval does not overlap:
  That means it starts strictly after the last inserted interval ends. In that case, we cannot merge them. We simply append the current interval as a new block into finalIntervals, and it becomes the new last inserted interval.
Step 3: Return the result.
After we’ve scanned all intervals, finalIntervals holds the merged, non-overlapping intervals in sorted order.

Why This Works

Sorted input enables local merging:
Once intervals are sorted by their start time, any possible overlap can only occur with the most recently inserted interval in the result. Earlier intervals are guaranteed to end before the current one starts, so there’s no need to look back further.
Output correctness:
The finalIntervals list remains sorted and non-overlapping because all overlapping ranges are merged as they are processed.

Time Complexity

Sorting the intervals takes O(N log N), where N is the number of intervals. After that, we scan through the sorted list once and either merge or append each interval in O(N) time. The total time complexity is O(N log N).

Space Complexity

We build the finalIntervals array (the output array) to store the merged result. In the worst case — when no intervals overlap — the result still contains at most N intervals, where N is the number of input intervals.

Apart from this output array, we only maintain a few simple variables. Therefore, the overall space complexity is O(N) if we include the output array, or O(1) if we exclude it.

Input-1

Merge Intervals - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

High-Level Strategy

Why This Works

Time Complexity

Space Complexity