Why Intervals Are a Common Problem Pattern in DSA C - Why This Pattern

Mental Model

Intervals represent ranges of values that often overlap or need merging, making them a common pattern in problems involving scheduling or grouping.

Analogy: Imagine booking meeting rooms where each meeting has a start and end time; you need to see which meetings overlap or fit together without conflict.

Time line:
0    1    2    3    4    5    6    7    8
|----|----|----|----|----|----|----|----|
Interval A:    [====]
Interval B:         [=======]
Interval C:               [==]

Dry Run Walkthrough

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

Goal: Understand how overlapping intervals cause problems and why merging them is useful

Step 1: Look at first two intervals [1,3] and [2,6]

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

Why: They overlap because 2 is inside [1,3], so they need to be merged

Step 2: Merge [1,3] and [2,6] into [1,6]

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

Why: Merging reduces complexity by combining overlapping intervals into one

Step 3: Check next interval [8,10] against merged [1,6]

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

Why: No overlap since 8 > 6, so keep separate

Step 4: Check last interval [15,18] against previous intervals

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

Why: No overlap, so keep separate

Result:

[1,6], [8,10], [15,18] -- merged intervals showing combined ranges

Annotated Code

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) {
    if (n <= 0) return;

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

    int index = 0; // index of last merged interval

    for (int i = 1; i < n; i++) {
        if (intervals[index].end >= intervals[i].start) {
            // Overlapping intervals, merge
            if (intervals[index].end < intervals[i].end) {
                intervals[index].end = intervals[i].end; // extend end
            }
        } else {
            index++;
            intervals[index] = intervals[i]; // move non-overlapping interval
        }
    }

    // Print merged intervals
    for (int i = 0; i <= index; i++) {
        printf("[%d,%d]", intervals[i].start, intervals[i].end);
        if (i < index) printf(", ");
    }
    printf("\n");
}

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

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

sort intervals to process them in order of start time

if (intervals[index].end >= intervals[i].start) {

check if current interval overlaps with last merged interval

intervals[index].end = intervals[i].end;

extend the end of merged interval if needed

index++; intervals[index] = intervals[i];

move to next merged interval when no overlap

Output

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

Complexity Analysis

Time: O(n log n) because sorting the intervals dominates the time

Space: O(1) because merging is done in place without extra storage

vs Alternative: Naive approach checks every pair for overlap O(n^2), which is slower than sorting + one pass

Edge Cases

Empty list of intervals

Function returns immediately without error

DSA C

if (n <= 0) return;

Intervals with no overlaps

All intervals remain separate after merge

DSA C

else { index++; intervals[index] = intervals[i]; }

Intervals fully contained inside others

Smaller intervals merge into larger ones correctly

DSA C

if (intervals[index].end < intervals[i].end) { intervals[index].end = intervals[i].end; }

When to Use This Pattern

When you see problems involving ranges or times that may overlap, think of the intervals pattern because merging or comparing ranges simplifies the problem.

Common Mistakes

Mistake: Not sorting intervals before merging
Fix: Always sort intervals by start time first to ensure correct merging order

Mistake: Not updating the end of merged interval correctly
Fix: Update the end to the max of overlapping intervals to cover full range

Summary

It shows why intervals often overlap and need merging in problems.

Use it when handling ranges like meeting times or number spans.

The key is sorting intervals first to merge overlaps easily.