Non Overlapping 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_KEPT = 'last_kept', LAST_KEPT_COLOR = 'black';
const KEPT_INTERVAL = 'kept_interval', KEPT_INTERVAL_COLOR = 'green';
const REMOVED_INTERVAL = 'removed_interval', REMOVED_INTERVAL_COLOR = 'red';

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

    startPartialBatch();
    const intervals = new VisArray(...inputIntervals).options({ labelExtractionPolicy: JSON.stringify });
    notification(`
        📌 <b>Step 1: Sort all intervals by their end time (earliest finish first).</b><br>
        The key insight is that <b>removing the fewest intervals</b> can be achieved by greedily
        <b>keeping the earliest-finishing non-overlapping intervals</b> — since each early finisher leaves
        the most room for future intervals.<br><br>
        To make these greedy choices efficiently, we first sort all intervals by their end time.
    `);

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

    notification(`
        ✅ Intervals are now sorted by end time.<br>
        We’re ready to scan and decide which intervals to keep and which ones must be removed.
    `);
    endBatch();

    let endOfLastInterval = -Infinity;
    let removalCount = 0;
    let index = 0;

    startPartialBatch();
    makeVisVariable(endOfLastInterval).options({ label: "endOfLastInterval" }).createVis();
    makeVisVariable(removalCount).options({ label: "removalCount" }).createVis();
    makeVisVariable(index).registerAsIndexPointer(intervals, CURRENT);
    notification(`
        📌 <b>Step 2: Scan through the sorted intervals.</b><br>
        We keep track of:<br>
        • <code>endOfLastInterval</code> = the end time of the last interval we decided to keep so far<br>
        • <code>removalCount</code> = how many intervals we’ve had to skip (remove)<br><br>
        We’ll move the ${makeColoredSpan('current index', CURRENT_COLOR)} across the list and, for each interval, decide:
        <b>keep it</b> (no overlap) or <b>remove it</b> (overlap).
    `);
    endBatch();

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

        if (currentInterval[0] >= endOfLastInterval) {
            notification(`
                ✅ Interval ${JSON.stringify(currentInterval)} does <b>not</b> overlap with the last kept interval. Therefore, we <b>keep</b> this interval.<br>
                Since the intervals are <b>sorted by end time</b>, this interval naturally ends after all previously kept ones,
                so when we keep it we can safely update <code>endOfLastInterval</code> to ${currentInterval[1]} (its end time).
                ${generateIntervalsComparisionSvg(endOfLastInterval, currentInterval, KEPT_INTERVAL_COLOR)}
            `);
            endOfLastInterval = currentInterval[1];
        } else {
            notification(`
                ❌ Interval ${JSON.stringify(currentInterval)} <b>overlaps</b> with the last kept interval (which ends at ${endOfLastInterval}).<br>
                Because the intervals are <b>sorted by end time</b>, this overlapping interval must finish <b>later</b> than the one we’ve already kept.<br><br>
                We therefore <b>remove</b> this interval and leave <code>endOfLastInterval</code> unchanged — keeping the earlier finisher is the greedy choice that preserves the most room for future intervals.<br><br>
                ${generateIntervalsComparisionSvg(endOfLastInterval, currentInterval, REMOVED_INTERVAL_COLOR)}
            `);
            removalCount += 1;
        }

        index += 1;
        endBatch();
    }

    notification(`
        🏁 <b>Finished.</b><br>
        The minimum number of intervals to remove to make the rest non-overlapping is: <b>${removalCount}</b>.
    `);

    return removalCount;
}

function generateIntervalsComparisionSvg(endOfLastInterval, currentInterval, currentIntervalColor) {
    return generateIntervalsSvgContent([
        endOfLastInterval !== -Infinity
            ? [[endOfLastInterval, endOfLastInterval, { text: "End of Last Kept Interval", color: LAST_KEPT_COLOR }]]
            : [],
        [[...currentInterval, { text: "Current Interval", color: currentIntervalColor }]]
    ]);
}

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

function colorSchemaAndExpanationNotification() {
    explanationNotification();
    notification(`
        🎨 <b>Color Schema:</b><br>
        • ${makeColoredSpan('Current Interval', CURRENT_COLOR)} — the interval currently being examined in the sorted list.<br>
        • ${makeColoredSpan('End of Last Kept Interval', LAST_KEPT_COLOR)} — a marker showing where the most recently kept interval ends; used to check for overlaps.<br>
        • ${makeColoredSpan('Kept Interval', KEPT_INTERVAL_COLOR)} — intervals that are safely kept (non-overlapping).<br>
        • ${makeColoredSpan('Removed Interval', REMOVED_INTERVAL_COLOR)} — intervals that overlap with the last kept one and must be removed.
    `);
}

Approach

We are given a list of intervals, and some of them may overlap. Our goal is to remove the minimum number of intervals so that no two remaining intervals overlap.

The key insight is that removing the fewest intervals can be achieved by greedily keeping the earliest-finishing non-overlapping intervals. Each early finisher leaves the most room for future intervals, so by always choosing the interval that ends first among those compatible with previous choices, we ensure the minimum number of removals overall.

High-Level Strategy

Step 1: Sort by end time.
To apply the greedy strategy of keeping the earliest-finishing intervals, we first sort all intervals in ascending order of their end time (earliest finish first).
This way, as we process them from left to right, each new interval we encounter is the next earliest finisher among the remaining ones — making it easy to decide which intervals to keep or remove.
Step 2: Scan and count removals.
Initialize two variables:
- endOfLastInterval — the end time of the last interval we decided to keep.
- removalCount — how many intervals we have to remove due to overlaps.
Then, iterate through each interval currentInterval:
- If currentInterval starts at or after endOfLastInterval,
  it does not overlap with the last kept one. We can safely keep it and update endOfLastInterval to this interval’s end time.
  
  Since intervals are sorted by end time, this one ends after all previously kept intervals, so using its end directly is safe for future comparisons.
- If the currentInterval starts before endOfLastInterval,
  it overlaps with the last kept one. Because the list is sorted by end time, this overlapping interval must finish later than the last kept one.
  
  Therefore, we remove it (increment removalCount) and do not change endOfLastInterval, which is known to be the earlier finisher than the currentInterval — the greedy choice that leaves more space for future intervals.
Step 3: Return the total number of removals.
Once we finish scanning all intervals, removalCount represents the smallest number of intervals that must be removed to make the list non-overlapping.

Why This Works

Sorting by end time enables greedy skipping:
Each time we encounter an overlap, we can be sure the current interval ends later than the previously kept one — so keeping it would only block more future intervals.
We only compare against the last kept interval:
We always update endOfLastInterval to the end of the last non-overlapping interval. We can safely use it as a single reference point for deciding whether to keep the current interval, without needing to check any of the earlier ones. This works because we know that no previously kept interval ends earlier than it.
The count directly measures the removals needed:
Instead of explicitly building the non-overlapping list, we just count how many intervals we skip. That count is the minimal number of removals required.

Time Complexity

Sorting the intervals by end time takes O(N log N), where N is the number of intervals. Then we make a single left-to-right pass, checking each interval once (O(N)), giving a total time complexity of O(N log N).

Space Complexity

The greedy scan itself uses only a few scalar variables, giving an O(1) space complexity.
However, since we sort the input first, the overall space complexity depends on the sorting algorithm: typically O(1), O(log N), or O(N).

Input-1

Non Overlapping Intervals - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

High-Level Strategy

Why This Works

Time Complexity

Space Complexity