Merge Overlapping Intervals in DSA C

Mental Model

We combine intervals that overlap into one bigger interval so no two intervals cover the same range twice.

Analogy: Imagine booking meeting rooms. If two meetings overlap in time, you merge them into one longer meeting to avoid confusion.

Intervals before merge:
[1,3] -> [2,6] -> [8,10] -> [15,18] -> null

Dry Run Walkthrough

Input: intervals: [1,3], [2,6], [8,10], [15,18]

Goal: Merge all overlapping intervals into combined intervals without overlaps

Step 1: Sort intervals by start time

[1,3] -> [2,6] -> [8,10] -> [15,18] -> null

Why: Sorting helps to easily find overlapping intervals by comparing neighbors

Step 2: Start with first interval [1,3] in merged list

Merged: [1,3]

Why: We need a base interval to compare others against

Step 3: Compare next interval [2,6] with last merged [1,3], they overlap

Merged: [1,6]

Why: Since 2 ≤ 3, intervals overlap, so merge by extending end to max(3,6)=6

Step 4: Compare next interval [8,10] with last merged [1,6], no overlap

Merged: [1,6] -> [8,10]

Why: 8 > 6 means no overlap, so add new interval

Step 5: Compare next interval [15,18] with last merged [8,10], no overlap

Merged: [1,6] -> [8,10] -> [15,18]

Why: 15 > 10 means no overlap, so add new interval

Result:

Merged intervals:
[1,6] -> [8,10] -> [15,18] -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define interval structure
typedef struct {
    int start;
    int end;
} Interval;

// Comparator for qsort to sort intervals by start time
int compare(const void *a, const void *b) {
    Interval *i1 = (Interval *)a;
    Interval *i2 = (Interval *)b;
    return i1->start - i2->start;
}

// Function to merge overlapping intervals
// intervals: input array, n: number of intervals
// merged: output array to store merged intervals
// returns number of merged intervals
int mergeIntervals(Interval intervals[], int n, Interval merged[]) {
    if (n == 0) return 0;

    // Sort intervals by start time
    qsort(intervals, n, sizeof(Interval), compare);

    int idx = 0; // index for merged array
    merged[0] = intervals[0]; // start with first interval

    for (int i = 1; i < n; i++) {
        // If current interval overlaps with last merged
        if (intervals[i].start <= merged[idx].end) {
            // Merge by extending the end if needed
            if (intervals[i].end > merged[idx].end) {
                merged[idx].end = intervals[i].end;
            }
        } else {
            // No overlap, add new interval
            idx++;
            merged[idx] = intervals[i];
        }
    }

    return idx + 1; // number of merged intervals
}

// Helper to print intervals
void printIntervals(Interval intervals[], int n) {
    for (int i = 0; i < n; i++) {
        printf("[%d,%d]", intervals[i].start, intervals[i].end);
        if (i != n - 1) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    Interval intervals[] = {{1,3}, {2,6}, {8,10}, {15,18}};
    int n = sizeof(intervals) / sizeof(intervals[0]);
    Interval merged[n];

    int mergedCount = mergeIntervals(intervals, n, merged);

    printf("Merged intervals:\n");
    printIntervals(merged, mergedCount);

    return 0;
}

qsort(intervals, n, sizeof(Interval), compare);

Sort intervals by start time to prepare for merging

merged[0] = intervals[0];

Initialize merged list with first interval

if (intervals[i].start <= merged[idx].end) {

Check if current interval overlaps with last merged interval

if (intervals[i].end > merged[idx].end) { merged[idx].end = intervals[i].end; }

Extend the end of merged interval if current interval ends later

else { idx++; merged[idx] = intervals[i]; }

No overlap, add current interval as new merged interval

Output

Merged intervals:

[1,6] -> [8,10] -> [15,18] -> null

Complexity Analysis

Time: O(n log n) because we sort all intervals first, then merge in one pass O(n)

Space: O(n) for the output array to store merged intervals

vs Alternative: Naive approach compares every pair leading to O(n^2), sorting reduces it to O(n log n)

Edge Cases

empty intervals array

returns zero merged intervals without error

DSA C

if (n == 0) return 0;

all intervals non-overlapping

merged intervals equal original intervals

DSA C

else { idx++; merged[idx] = intervals[i]; }

all intervals fully overlapping

merged intervals is a single interval covering all

DSA C

if (intervals[i].start <= merged[idx].end) { if (intervals[i].end > merged[idx].end) { merged[idx].end = intervals[i].end; } }

When to Use This Pattern

When you see a list of intervals and need to combine overlapping ones, use the merge intervals pattern by sorting and merging neighbors.

Common Mistakes

Mistake: Not sorting intervals before merging, causing incorrect merges
Fix: Always sort intervals by start time before merging

Mistake: Not updating the end of merged interval when current interval extends beyond it
Fix: Update merged interval end to max of current and merged ends

Summary

It merges overlapping intervals into combined intervals without overlaps.

Use it when you need to simplify or combine ranges that may overlap.

Sort intervals by start time first, then merge neighbors by comparing ends.

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