Merge Overlapping Intervals in DSA C - Time & Space Complexity

Time Complexity: Merge Overlapping Intervals

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to merge overlapping intervals changes as the number of intervals grows.

Specifically, how does the work increase when we have more intervals to merge?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int compare(const void *a, const void *b) {
    return ((int (*)[2])a)[0][0] - ((int (*)[2])b)[0][0];
}

// Merge overlapping intervals in an array
void mergeIntervals(int intervals[][2], int n) {
    // Sort intervals by start time
    qsort(intervals, n, sizeof(intervals[0]), compare);

    int index = 0; // stores index of last merged interval
    for (int i = 1; i < n; i++) {
        if (intervals[index][1] >= intervals[i][0]) {
            if (intervals[index][1] < intervals[i][1])
                intervals[index][1] = intervals[i][1];
        } else {
            index++;
            intervals[index][0] = intervals[i][0];
            intervals[index][1] = intervals[i][1];
        }
    }
}
    

This code sorts intervals by their start time, then merges overlapping ones by updating the end time or moving to the next interval.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the intervals and then one loop to merge them.
• How many times: Sorting takes multiple comparisons depending on n, and the loop runs once through all intervals.

How Execution Grows With Input

Sorting grows faster than just looping, so it dominates the time.

Input Size (n)	Approx. Operations
10	About 10 log 10 ≈ 33 operations for sorting + 10 for merging
100	About 100 log 100 ≈ 664 operations for sorting + 100 for merging
1000	About 1000 log 1000 ≈ 9966 operations for sorting + 1000 for merging

Pattern observation: As input grows, sorting cost grows faster than the simple loop, so total time grows roughly like n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to merge intervals grows a bit faster than just the number of intervals because sorting takes extra work.

Common Mistake

[X] Wrong: "Merging intervals only takes O(n) time because we just loop once."

[OK] Correct: Before merging, we must sort intervals, which takes more time than just looping, so total time is more than O(n).

Interview Connect

Understanding this time complexity helps you explain why sorting is important before merging and shows you can analyze combined steps clearly.

Self-Check

"What if the intervals were already sorted? How would the time complexity change?"