Non Overlapping Intervals Minimum Removal in DSA C - Execution Trace

Concept Flow - Non Overlapping Intervals Minimum Removal

Sort intervals by end time

↓

Initialize count=0, prev_end = -∞

↓

For each interval

↓

Check if current start >= prev_end?

No→Remove interval, count++

Yes↓

Update prev_end = current end

↓

Repeat for all intervals

↓

Return count

Sort intervals by their end time, then iterate to count how many intervals must be removed to avoid overlaps.

Execution Sample

DSA C

int cmp(const void *a, const void *b) {
  return ((int (*)[2])a)[0][1] - ((int (*)[2])b)[0][1];
}
int eraseOverlapIntervals(int intervals[][2], int n) {
  if (n <= 1) return 0;
  qsort(intervals, n, sizeof(intervals[0]), cmp);
  int count = 0, prev_end = intervals[0][1];
  for (int i = 1; i < n; i++) {
    if (intervals[i][0] < prev_end) count++;
    else prev_end = intervals[i][1];
  }
  return count;
}

This code sorts intervals by end time and counts minimum removals to avoid overlaps.

Execution Table

Step	Operation	Current Interval	Prev End	Overlap?	Count	Visual State
1	Sort intervals	[1,2], [2,3], [1,3], [3,4]	-	No	0	[1,2] -> [2,3] -> [1,3] -> [3,4]
2	Initialize	[1,2]	2	No	0	[1,2] -> [2,3] -> [1,3] -> [3,4]
3	Check interval	[2,3]	2	No	0	[1,2] -> [2,3] -> [1,3] -> [3,4]
4	Update prev_end	[2,3]	3	No	0	[1,2] -> [2,3] -> [1,3] -> [3,4]
5	Check interval	[1,3]	3	Yes	1	[1,2] -> [2,3] -> [1,3] (removed) -> [3,4]
6	Check interval	[3,4]	3	No	1	[1,2] -> [2,3] -> [1,3] (removed) -> [3,4]
7	Update prev_end	[3,4]	4	No	1	[1,2] -> [2,3] -> [3,4]
8	End	-	4	-	1	[1,2] -> [2,3] -> [3,4]

💡 All intervals checked; total removals = 1

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
count	0	0	1	1	1
prev_end	-	2	3	4	4

Key Moments - 3 Insights

Why do we update prev_end only when no overlap is found?

Because prev_end tracks the end of the last interval kept. If overlap occurs, we remove the current interval and do not update prev_end, as the previous interval remains.

Why do we sort intervals by their end time?

Sorting by end time ensures we always keep intervals that finish earliest, maximizing space for future intervals and minimizing removals, as shown in Step 1 of execution_table.

What happens if intervals have the same end time?

They are processed in order after sorting. Overlaps are detected by comparing start with prev_end, so intervals with same end time but overlapping starts will cause removals.

Visual Quiz - 3 Questions

Look at the execution_table at Step 7, what is the count value?

A 2

B 0

C 1

D 3

💡 Hint

Check the 'Count' column at Step 7 in execution_table.

At which step does prev_end update to 3?

A Step 4

B Step 6

C Step 5

D Step 3

💡 Hint

Look at the 'prev_end' column changes in execution_table rows.

If the first interval was [1,5] instead of [1,2], how would count change?

A It would stay the same

B It would increase

C It would decrease

D Cannot determine

💡 Hint

Consider how a longer first interval affects overlaps and removals in the execution_table.

Concept Snapshot

Non Overlapping Intervals Minimum Removal:
- Sort intervals by end time
- Initialize count=0, prev_end = first interval end
- For each interval, if start < prev_end, increment count (remove)
- Else update prev_end
- Return count as minimum removals

Full Transcript

To find the minimum number of intervals to remove so that the rest do not overlap, first sort intervals by their end times. Initialize a count of removals to zero and set prev_end to the end of the first interval. Iterate through each interval starting from the second. If the current interval's start is less than prev_end, it overlaps, so increment count and do not update prev_end. Otherwise, update prev_end to the current interval's end. After checking all intervals, the count represents the minimum removals needed.

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