Merge Overlapping Intervals in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging overlapping intervals

What is the output of the following code that merges overlapping intervals?

DSA C

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int start;
    int end;
} Interval;

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

void mergeIntervals(Interval intervals[], int n, Interval result[], int *resSize) {
    if (n <= 0) {
        *resSize = 0;
        return;
    }
    qsort(intervals, n, sizeof(Interval), compare);
    int index = 0;
    result[0] = intervals[0];
    for (int i = 1; i < n; i++) {
        if (result[index].end >= intervals[i].start) {
            if (result[index].end < intervals[i].end) {
                result[index].end = intervals[i].end;
            }
        } else {
            index++;
            result[index] = intervals[i];
        }
    }
    *resSize = index + 1;
}

int main() {
    Interval intervals[] = {{1,3}, {2,6}, {8,10}, {15,18}};
    int n = 4;
    Interval result[10];
    int resSize = 0;
    mergeIntervals(intervals, n, result, &resSize);
    for (int i = 0; i < resSize; i++) {
        printf("%d->%d ", result[i].start, result[i].end);
    }
    return 0;
}

A 1->6 8->10 15->18

B 1->3 2->6 8->10 15->18

C 1->6 2->6 8->10 15->18

D 1->3 6->10 15->18

💡 Hint

Think about how intervals that overlap are combined into one.

The code sorts intervals by start time, then merges overlapping intervals by extending the end time. Intervals {1,3} and {2,6} overlap and merge into {1,6}. Others remain separate.

🧠 Conceptual

intermediate

Number of merged intervals

Given intervals {{1,4}, {4,5}}, how many intervals remain after merging overlapping intervals?

A 3

B 2

C 0

D 1

💡 Hint

Intervals that touch at the boundary are considered overlapping.

Intervals {1,4} and {4,5} overlap at point 4, so they merge into {1,5}, resulting in 1 interval.

🔧 Debug

advanced

Identify the error in merging intervals code

What error will this code produce when merging intervals? Code snippet: void mergeIntervals(Interval intervals[], int n, Interval result[], int *resSize) { qsort(intervals, n, sizeof(Interval), compare); int index = 0; result[0] = intervals[0]; for (int i = 1; i <= n; i++) { if (result[index].end >= intervals[i].start) { if (result[index].end < intervals[i].end) { result[index].end = intervals[i].end; } } else { index++; result[index] = intervals[i]; } } *resSize = index + 1; }

A Logical error: intervals not merged correctly

B Compilation error: missing semicolon

C Runtime error: accessing out of bounds array element

D No error, code runs fine

💡 Hint

Check the loop boundary condition carefully.

The for loop runs with i <= n, which accesses intervals[n], out of array bounds causing runtime error.

❓ Predict Output

advanced

Output after merging intervals with nested overlaps

What is the output of merging these intervals: {{1,10}, {2,3}, {4,5}, {6,7}, {8,9}}?

DSA C

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int start;
    int end;
} Interval;

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

void mergeIntervals(Interval intervals[], int n, Interval result[], int *resSize) {
    qsort(intervals, n, sizeof(Interval), compare);
    int index = 0;
    result[0] = intervals[0];
    for (int i = 1; i < n; i++) {
        if (result[index].end >= intervals[i].start) {
            if (result[index].end < intervals[i].end) {
                result[index].end = intervals[i].end;
            }
        } else {
            index++;
            result[index] = intervals[i];
        }
    }
    *resSize = index + 1;
}

int main() {
    Interval intervals[] = {{1,10}, {2,3}, {4,5}, {6,7}, {8,9}};
    int n = 5;
    Interval result[10];
    int resSize = 0;
    mergeIntervals(intervals, n, result, &resSize);
    for (int i = 0; i < resSize; i++) {
        printf("%d->%d ", result[i].start, result[i].end);
    }
    return 0;
}

A 1->10 2->3 4->5 6->7 8->9

B 1->10

C 1->3 4->10

D 1->3 4->5 6->7 8->9 10->10

💡 Hint

All smaller intervals are inside the first big interval.

Since {1,10} covers all other intervals, they merge into one interval {1,10}.

🧠 Conceptual

expert

Minimum number of intervals after merging complex overlaps

Given intervals {{1,5}, {2,6}, {8,10}, {9,12}, {15,20}, {18,22}}, what is the minimum number of intervals after merging all overlaps?

A 3

B 5

C 2

D 4

💡 Hint

Group intervals that overlap or touch each other.

Intervals {1,5} and {2,6} merge into {1,6}. Intervals {8,10} and {9,12} merge into {8,12}. Intervals {15,20} and {18,22} merge into {15,22}. So total 3 merged intervals.