Non Overlapping Intervals Minimum Removal in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum removals for overlapping intervals

What is the output of the following code that calculates the minimum number of intervals to remove to avoid overlaps?

DSA C

int intervals[][2] = {{1,3},{2,4},{3,5},{6,7}};
int n = 4;

// Sort intervals by end time
for(int i=0; i<n-1; i++) {
    for(int j=0; j<n-i-1; j++) {
        if(intervals[j][1] > intervals[j+1][1]) {
            int temp0 = intervals[j][0];
            int temp1 = intervals[j][1];
            intervals[j][0] = intervals[j+1][0];
            intervals[j][1] = intervals[j+1][1];
            intervals[j+1][0] = temp0;
            intervals[j+1][1] = temp1;
        }
    }
}

int count = 1;
int end = intervals[0][1];
for(int i=1; i<n; i++) {
    if(intervals[i][0] >= end) {
        count++;
        end = intervals[i][1];
    }
}

int result = n - count;
printf("%d\n", result);

A 1

B 2

C 3

D 0

💡 Hint

Think about how many intervals can fit without overlapping after sorting by end time.

The code sorts intervals by their end time and greedily counts the maximum number of non-overlapping intervals. The minimum removals is total intervals minus this count. Here, 3 intervals can be non-overlapping, so 1 must be removed.

🧠 Conceptual

intermediate

Understanding the greedy choice in interval removal

Why does sorting intervals by their end time help in minimizing the number of intervals to remove to avoid overlaps?

A Because intervals with earliest start time always overlap less.

B Because sorting by length of intervals guarantees minimal removals.

C Because sorting by start time ensures maximum intervals are removed.

D Because choosing intervals with earliest end time leaves more room for following intervals.

💡 Hint

Think about how the end time affects the possibility of fitting more intervals after it.

Choosing intervals that end earliest allows more intervals to fit after them without overlapping, minimizing removals.

🔧 Debug

advanced

Identify the bug in interval sorting code

What is the bug in the following code snippet that sorts intervals by their end time? for(int i=0; i intervals[j+1][1]) { int temp0 = intervals[j][0]; int temp1 = intervals[j][1]; intervals[j][0] = intervals[j+1][0]; intervals[j][1] = intervals[j+1][1]; intervals[j+1][0] = temp0; intervals[j+1][1] = temp1; } } }

A Swapping intervals incorrectly swaps only end times, not start times.

B The inner loop should run until j < n-i, not n-i-1.

C No bug, the code correctly sorts intervals by end time.

D The swap logic is correct but inefficient; no bug affects correctness.

💡 Hint

Check carefully how the swap is done for both start and end times.

The code correctly swaps both start and end times of intervals to sort by end time using bubble sort.

❓ Predict Output

advanced

Output of minimum removals with overlapping intervals

What is the output of the following code snippet?

DSA C

int intervals[][2] = {{1,2},{2,3},{3,4},{1,3}};
int n = 4;

// Sort intervals by end time
for(int i=0; i<n-1; i++) {
    for(int j=0; j<n-i-1; j++) {
        if(intervals[j][1] > intervals[j+1][1]) {
            int temp0 = intervals[j][0];
            int temp1 = intervals[j][1];
            intervals[j][0] = intervals[j+1][0];
            intervals[j][1] = intervals[j+1][1];
            intervals[j+1][0] = temp0;
            intervals[j+1][1] = temp1;
        }
    }
}

int count = 1;
int end = intervals[0][1];
for(int i=1; i<n; i++) {
    if(intervals[i][0] >= end) {
        count++;
        end = intervals[i][1];
    }
}

int result = n - count;
printf("%d\n", result);

A 1

B 2

C 3

D 0

💡 Hint

Count how many intervals can be chosen without overlap after sorting by end time.

The code sorts intervals by their end time and greedily counts the maximum number of non-overlapping intervals. The minimum removals is total intervals minus this count. Here, 3 intervals can be non-overlapping, so 1 must be removed.

🧠 Conceptual

expert

Why greedy approach works for minimum interval removals

Which statement best explains why the greedy approach of selecting intervals by earliest end time guarantees the minimum number of removals to avoid overlaps?

A Because it tries all possible combinations of intervals to find the minimum removals.

B Because selecting intervals with earliest end time always leads to the globally optimal solution by maximizing remaining space.

C Because it removes the longest intervals first to minimize overlap.

D Because it sorts intervals by start time and removes those that start too early.

💡 Hint

Think about how the greedy choice leaves room for future intervals.

Choosing intervals with earliest end time leaves the maximum room for subsequent intervals, ensuring the maximum number of intervals remain without overlap, thus minimizing removals.

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