Non Overlapping Intervals Minimum Removal in DSA C - Build from Scratch

Non Overlapping Intervals Minimum Removal

📖 Scenario: You are organizing a schedule of meetings represented as time intervals. Some meetings overlap, and you want to remove the minimum number of meetings so that the remaining meetings do not overlap.

🎯 Goal: Build a program that finds the minimum number of intervals to remove to make the rest of the intervals non-overlapping.

📋 What You'll Learn

Create an array of intervals with exact values

Add a variable to count removals

Implement the logic to find minimum removals using sorting and iteration

Print the final count of intervals to remove

💡 Why This Matters

🌍 Real World

Scheduling meetings, booking rooms, or managing tasks without conflicts is common in workplaces and apps.

💼 Career

Understanding interval scheduling and greedy algorithms is useful for software engineers working on calendar apps, resource allocation, and optimization problems.

1

Create the intervals array

Create an array of intervals called intervals with these exact pairs: {1, 3}, {2, 4}, {3, 5}, {6, 7}, {8, 10}, {9, 11}.

DSA C

// Define the intervals array with given pairs
// Your code here

Hint

Use a struct for intervals and initialize the array with the exact pairs.

2

Add a variable to count removals

Add an integer variable called removals and set it to 0 to count how many intervals we remove.

DSA C

#include 

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

Interval intervals[] = {
    {1, 3},
    {2, 4},
    {3, 5},
    {6, 7},
    {8, 10},
    {9, 11}
};

int n = sizeof(intervals) / sizeof(intervals[0]);

// Add an integer variable removals and set it to 0
// Your code here

Hint

Just declare and initialize the variable before main logic.

3

Implement the minimum removal logic

Write a function called compare to sort intervals by their end time. Then, in main, sort the intervals array using qsort. After sorting, use a for loop with variable i from 1 to n - 1 to count how many intervals overlap and increase removals accordingly.

DSA C

int compare(const void *a, const void *b) {
    Interval *i1 = (Interval *)a;
    Interval *i2 = (Interval *)b;
    return i1->end - i2->end;
}
int main() {
    qsort(intervals, n, sizeof(Interval), compare);
    int end = intervals[0].end;
    for (int i = 1; i < n; i++) {
        if (intervals[i].start < end) {
            removals++;
        } else {
            end = intervals[i].end;
        }
    }
    // Print the result
    printf("%d\n", removals);
    return 0;
}

Hint

Sort intervals by end time, then count overlaps by comparing start with last end.

4

Print the minimum removals

Write a printf statement to print the value of removals followed by a newline.

DSA C

#include 
#include 

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

Interval intervals[] = {
    {1, 3},
    {2, 4},
    {3, 5},
    {6, 7},
    {8, 10},
    {9, 11}
};

int n = sizeof(intervals) / sizeof(intervals[0]);

int removals = 0;

int compare(const void *a, const void *b) {
    Interval *i1 = (Interval *)a;
    Interval *i2 = (Interval *)b;
    return i1->end - i2->end;
}

int main() {
    qsort(intervals, n, sizeof(Interval), compare);

    int end = intervals[0].end;

    for (int i = 1; i < n; i++) {
        if (intervals[i].start < end) {
            removals++;
        } else {
            end = intervals[i].end;
        }
    }

    // Print the value of removals
    // Your code here
    return 0;
}

Hint

Use printf("%d\n", removals); to print the count.

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