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.

Practice

1. What is the main goal of the Merge Overlapping Intervals problem?

easy

A. Find the maximum number of intervals without overlap

B. Sort intervals by their end times only

C. Combine all intervals that overlap into one continuous interval

D. Count how many intervals are in the list

Solution

1. Step 1: Understand the problem goal

   The problem asks to merge intervals that overlap, so they become one continuous interval without gaps.

2. Step 2: Identify the correct description

   Combine all intervals that overlap into one continuous interval correctly describes merging overlapping intervals into one combined interval.

3. Final Answer:

   Combine all intervals that overlap into one continuous interval -> Option C

4. Quick Check:

   Merge overlapping intervals = Combine overlaps [OK]

Hint: Think of joining overlapping time slots into one [OK]

Common Mistakes:

• Confusing merging with sorting only
• Counting intervals instead of merging
• Ignoring overlaps

2. Which of the following C code snippets correctly sorts intervals by their start time before merging?

easy

A. qsort(intervals, n, sizeof(Interval), compareStart);

B. qsort(intervals, n, sizeof(Interval), compareLength);

C. sort(intervals.begin(), intervals.end());

D. qsort(intervals, n, sizeof(Interval), compareEnd);

Solution

1. Step 1: Identify sorting criteria for merging

   Intervals must be sorted by their start time to merge correctly.

2. Step 2: Match sorting function

   qsort(intervals, n, sizeof(Interval), compareStart); uses compareStart which sorts by start time, correct for merging.

3. Final Answer:

   qsort(intervals, n, sizeof(Interval), compareStart); -> Option A

4. Quick Check:

   Sort by start time = qsort with compareStart [OK]

Hint: Sort intervals by start time before merging [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Using C++ sort syntax in C code
• Sorting by interval length

3. What is the output of the merged intervals after running this code on input intervals: [[1,3], [2,6], [8,10], [15,18]]?

Intervals = [[1,3], [2,6], [8,10], [15,18]]
// After sorting by start time
// Merge overlapping intervals
// Print merged intervals

medium

A. [[1,6], [8,10], [15,18]]

B. [[1,3], [2,6], [8,10], [15,18]]

C. [[1,6], [2,10], [15,18]]

D. [[1,6], [8,15], [18,18]]

Solution

1. Step 1: Sort intervals by start time

   Intervals are already sorted: [1,3], [2,6], [8,10], [15,18].

2. Step 2: Merge overlapping intervals

   [1,3] and [2,6] overlap, merge to [1,6]. Others do not overlap.

3. Final Answer:

   [[1,6], [8,10], [15,18]] -> Option A

4. Quick Check:

   Merged intervals = [[1,6], [8,10], [15,18]] [OK]

Hint: Merge intervals if current start ≤ previous end [OK]

Common Mistakes:

• Not merging overlapping intervals
• Merging non-overlapping intervals
• Incorrectly merging intervals with gaps

4. Identify the bug in this C code snippet for merging intervals:

Interval merged[100];
int m = 0;
merged[0] = intervals[0];
for (int i = 1; i < n; i++) {
  if (intervals[i].start <= merged[m].end) {
    merged[m].end = intervals[i].end;
  } else {
    m++;
    merged[m] = intervals[i];
  }
}

medium

A. Loop starts from 0 instead of 1

B. It incorrectly updates the end of the previous interval without checking max end

C. Uses <= instead of < in the overlap condition

D. It compares start with start instead of end

Solution

1. Step 1: Analyze interval merging logic

   When intervals overlap, end should be max of both ends, not just assigned.

2. Step 2: Identify incorrect update

   Code sets previous end to current end without max check, causing wrong merges.

3. Final Answer:

   It incorrectly updates the end of the previous interval without checking max end -> Option B

4. Quick Check:

   Use max end when merging intervals [OK]

Hint: Always update end to max of overlapping intervals [OK]

Common Mistakes:

• Assigning end without max check
• Using strict < instead of <= for touching intervals
• Wrong loop start index

5. Given intervals [[1,4], [4,5], [5,6], [7,8]], what is the merged output if intervals that touch at boundaries are considered overlapping?

hard

A. [[1,8]]

B. [[1,4], [4,5], [5,6], [7,8]]

C. [[1,5], [5,6], [7,8]]

D. [[1,6], [7,8]]

Solution

1. Step 1: Understand touching intervals as overlapping

   Intervals that share boundary points merge: [1,4] and [4,5] merge to [1,5], then with [5,6] to [1,6].

2. Step 2: Merge intervals accordingly

   After merging first three intervals, [7,8] remains separate.

3. Final Answer:

   [[1,6], [7,8]] -> Option D

4. Quick Check:

   Touching intervals merge into one [OK]

Hint: Treat intervals with end == start as overlapping [OK]

Common Mistakes:

• Not merging touching intervals
• Merging all intervals incorrectly
• Ignoring boundary overlap condition