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.