Non Overlapping Intervals Minimum Removal in DSA C

Mental Model

We want to remove the fewest intervals so that no intervals overlap. We do this by always keeping the interval that ends earliest to leave room for others.

Analogy: Imagine scheduling meetings in one room. To fit the most meetings without overlap, always pick the meeting that finishes earliest, then schedule the next meeting that starts after it ends.

Intervals: [1,3] -> [2,4] -> [3,5] -> null
Goal: Remove minimum intervals so none overlap

Dry Run Walkthrough

Input: intervals: [1,3], [2,4], [3,5]

Goal: Remove the minimum number of intervals so that no two intervals overlap

Step 1: Sort intervals by end time

[1,3] -> [2,4] -> [3,5]

Why: Sorting by end time helps us pick intervals that finish earliest first

Step 2: Select first interval [1,3], set end = 3

Selected: [1,3], end=3

Why: We keep the first interval as a baseline to compare others

Step 3: Check next interval [2,4], start=2 < end=3, overlap found, remove it

Removed [2,4], count=1

Why: This interval overlaps with the last selected, so we remove it

Step 4: Check next interval [3,5], start=3 >= end=3, no overlap, select it, update end=5

Selected intervals: [1,3], [3,5]

Why: This interval starts after or at the end of last selected, so we keep it

Result:

Selected intervals: [1,3] -> [3,5] -> null
Minimum removals: 1

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Structure to represent an interval
typedef struct {
    int start;
    int end;
} Interval;

// Comparator function to sort intervals by end time
int compare(const void *a, const void *b) {
    Interval *i1 = (Interval *)a;
    Interval *i2 = (Interval *)b;
    return i1->end - i2->end;
}

// Function to find minimum number of intervals to remove
int eraseOverlapIntervals(Interval* intervals, int intervalsSize) {
    if (intervalsSize == 0) return 0;

    // Sort intervals by their end time
    qsort(intervals, intervalsSize, sizeof(Interval), compare);

    int count = 0; // count of removed intervals
    int end = intervals[0].end; // end time of last selected interval

    for (int i = 1; i < intervalsSize; i++) {
        if (intervals[i].start < end) {
            // Overlap found, remove this interval
            count++;
        } else {
            // No overlap, update end to current interval's end
            end = intervals[i].end;
        }
    }
    return count;
}

int main() {
    Interval intervals[] = {{1,3}, {2,4}, {3,5}};
    int size = sizeof(intervals) / sizeof(intervals[0]);
    int removals = eraseOverlapIntervals(intervals, size);
    printf("Minimum removals: %d\n", removals);
    return 0;
}

qsort(intervals, intervalsSize, sizeof(Interval), compare);

Sort intervals by their end time to prioritize earliest finishing

int end = intervals[0].end;

Initialize end to the end time of the first interval selected

if (intervals[i].start < end) { count++; } else { end = intervals[i].end; }

If current interval overlaps, increment removal count; else update end to current interval's end

Output

Minimum removals: 1

Complexity Analysis

Time: O(n log n) because we sort the intervals first, then do a single pass through them

Space: O(1) because sorting is done in place and only a few variables are used

vs Alternative: A naive approach checking all pairs for overlap would be O(n^2), so sorting plus one pass is more efficient

Edge Cases

empty intervals array

returns 0 removals since no intervals exist

DSA C

if (intervalsSize == 0) return 0;

all intervals non-overlapping

returns 0 removals because no overlaps exist

DSA C

if (intervals[i].start < end) { count++; } else { end = intervals[i].end; }

all intervals overlapping

removes all but one interval, returns intervalsSize - 1

DSA C

if (intervals[i].start < end) { count++; }

When to Use This Pattern

When asked to remove minimum intervals to avoid overlaps, reach for the greedy pattern of sorting by end time and selecting intervals that finish earliest.

Common Mistakes

Mistake: Sorting intervals by start time instead of end time
Fix: Sort intervals by their end time to ensure earliest finishing intervals are selected first

Mistake: Updating end time even when intervals overlap
Fix: Only update end time when the current interval does not overlap with the last selected

Summary

Removes the fewest intervals so that remaining intervals do not overlap.

Use when you need to schedule intervals with no conflicts by removing minimum intervals.

Always pick intervals that finish earliest to maximize room for others.