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.

Practice

1. What is the main goal of the Non Overlapping Intervals Minimum Removal problem?

easy

A. To find the minimum number of intervals to remove so that the rest do not overlap

B. To find the maximum number of overlapping intervals

C. To merge all intervals into one

D. To sort intervals by their start time

Solution

1. Step 1: Understand the problem goal

   The problem asks to remove the fewest intervals so that no two intervals overlap.

2. Step 2: Clarify what non-overlapping means

   Non-overlapping intervals do not share any common points except possibly at the boundary.

3. Final Answer:

   To find the minimum number of intervals to remove so that the rest do not overlap -> Option A

4. Quick Check:

   Minimum removal = non-overlapping intervals [OK]

Hint: Focus on removing intervals, not merging or counting overlaps [OK]

Common Mistakes:

• Confusing removal with merging intervals
• Thinking the goal is to count overlaps
• Assuming intervals can be rearranged

2. Which of the following C code snippets correctly sorts intervals by their end time for the minimum removal problem?

easy

A. qsort(intervals, n, sizeof(Interval), compareStart);

B. qsort(intervals, n, sizeof(Interval), compareEnd);

C. qsort(intervals, n, sizeof(Interval), compareLength);

D. qsort(intervals, n, sizeof(Interval), compareStartDesc);

Solution

1. Step 1: Identify sorting criteria for minimum removal

   Sorting intervals by their end time helps greedily select intervals that finish earliest.

2. Step 2: Match sorting function

   The function compareEnd sorts by end time, which is correct for this problem.

3. Final Answer:

   qsort(intervals, n, sizeof(Interval), compareEnd); -> Option B

4. Quick Check:

   Sort by end time = compareEnd [OK]

Hint: Sort intervals by end time to minimize removals [OK]

Common Mistakes:

• Sorting by start time instead of end time
• Sorting by interval length which is irrelevant
• Sorting in descending order of start time

3. What is the output of the following C code snippet that calculates minimum removals for intervals?

typedef struct { int start; int end; } Interval;

int minRemoval(Interval intervals[], int n) {
    qsort(intervals, n, sizeof(Interval), compareEnd);
    int count = 0, end = intervals[0].end;
    for (int i = 1; i < n; i++) {
        if (intervals[i].start < end) {
            count++;
        } else {
            end = intervals[i].end;
        }
    }
    return count;
}

// Intervals: {{1,3}, {2,4}, {3,5}}

int main() {
    Interval intervals[] = {{1,3}, {2,4}, {3,5}};
    int n = 3;
    printf("%d", minRemoval(intervals, n));
    return 0;
}

medium

A. 3

B. 2

C. 0

D. 1

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals by end: {1,3}, {2,4}, {3,5}

2. Step 2: Count overlaps and removals

   Start with end=3. Interval {2,4} starts at 2 < 3, so count=1. Interval {3,5} starts at 3 >= 3, update end=5.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   One overlap removed = 1 [OK]

Hint: Count intervals starting before last end time [OK]

Common Mistakes:

• Not sorting intervals before counting
• Counting intervals that do not overlap
• Updating end incorrectly

4. Identify the bug in this C function for minimum interval removal:

int minRemoval(Interval intervals[], int n) {
    qsort(intervals, n, sizeof(Interval), compareStart);
    int count = 0, end = intervals[0].end;
    for (int i = 1; i < n; i++) {
        if (intervals[i].start < end) {
            count++;
        } else {
            end = intervals[i].end;
        }
    }
    return count;
}

medium

A. Using compareStart instead of compareEnd in qsort

B. Not initializing count to zero

C. Loop starts from 0 instead of 1

D. Updating end inside the if condition

Solution

1. Step 1: Check sorting criteria

   The function sorts intervals by start time, but it should sort by end time for correct greedy selection.

2. Step 2: Understand impact of wrong sorting

   Sorting by start time can cause incorrect overlap counting and wrong removal count.

3. Final Answer:

   Using compareStart instead of compareEnd in qsort -> Option A

4. Quick Check:

   Sort by end time needed [OK]

Hint: Always sort by end time, not start time [OK]

Common Mistakes:

• Sorting by start time
• Incorrect loop index
• Wrong update of end variable

5. Given intervals {{1,2}, {2,3}, {3,4}, {1,3}}, what is the minimum number of intervals to remove to make the rest non-overlapping?

hard

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: {1,2}, {2,3}, {1,3}, {3,4}

2. Step 2: Select intervals greedily and count removals

   Select {1,2} first (end=2). {2,3} starts at 2 >= 2, select it (end=3). {1,3} starts at 1 < 3, remove it (count=1). {3,4} starts at 3 >= 3, select it.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   One removal needed to avoid overlap [OK]

Hint: Pick intervals ending earliest, remove overlaps [OK]

Common Mistakes:

• Removing too many intervals
• Not sorting intervals before processing
• Confusing overlapping intervals with touching intervals