Merge Intervals - Practice Coding Problems

Merge Intervals - Problem

Array Sorting Medium

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Two intervals overlap if they share at least one common point. For example, [1,3] and [2,6] overlap because they share the range [2,3].

Example: If you have intervals [[1,3],[2,6],[8,10],[15,18]], the first two intervals overlap and should be merged into [1,6], resulting in [[1,6],[8,10],[15,18]].

Input & Output

Example 1 — Basic Overlapping Intervals

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

› Output: [[1,6],[8,10],[15,18]]

💡 Note: Intervals [1,3] and [2,6] overlap (share range [2,3]), so merge them into [1,6]. The other intervals [8,10] and [15,18] don't overlap with anything.

Example 2 — All Intervals Merge

$ Input: intervals = [[1,4],[4,5]]

› Output: [[1,5]]

💡 Note: Intervals [1,4] and [4,5] overlap at point 4, so they merge into [1,5].

Example 3 — No Overlaps

$ Input: intervals = [[1,2],[3,4],[5,6]]

› Output: [[1,2],[3,4],[5,6]]

💡 Note: No intervals overlap, so the result is the same as input.

Constraints

1 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ start_i ≤ end_i ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of intervals with some overlapping

Identify Overlaps

Find intervals that share common points

Merge

Combine overlapping intervals into single intervals

Key Takeaway

🎯 Key Insight: Sorting by start time transforms the problem into a simple linear scan for overlaps

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to sort intervals by start time first, which allows us to merge overlapping intervals in a single linear pass. The optimal approach has O(n log n) time complexity due to sorting, and O(n) space for the result array.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n³)	O(1)	Compare every interval with every other interval to find overlaps
Sort Then Merge	O(n log n)	O(n)	Sort intervals by start time, then merge overlapping ones in linear pass

Brute Force - Check All Pairs — Algorithm Steps

Step 1: For each interval, find all overlapping intervals
Step 2: Merge overlapping intervals into one
Step 3: Repeat until no more merges possible

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare All Pairs

Check each interval against all others

Merge Overlaps

Combine overlapping intervals found

Repeat

Continue until no more merges possible

Code -

solution.c — C

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

int** solution(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
    if (intervalsSize == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    // Create a copy to work with
    int** result = (int**)malloc(intervalsSize * sizeof(int*));
    *returnColumnSizes = (int*)malloc(intervalsSize * sizeof(int));
    int resultSize = 0;
    
    for (int i = 0; i < intervalsSize; i++) {
        result[i] = (int*)malloc(2 * sizeof(int));
        result[i][0] = intervals[i][0];
        result[i][1] = intervals[i][1];
        (*returnColumnSizes)[i] = 2;
        resultSize++;
    }
    
    // Keep merging until no more overlaps
    int merged = 1;
    while (merged) {
        merged = 0;
        for (int i = 0; i < resultSize; i++) {
            for (int j = i + 1; j < resultSize; j++) {
                // Check if intervals overlap
                if (result[i][0] <= result[j][1] && result[j][0] <= result[i][1]) {
                    // Merge the intervals
                    result[i][0] = result[i][0] < result[j][0] ? result[i][0] : result[j][0];
                    result[i][1] = result[i][1] > result[j][1] ? result[i][1] : result[j][1];
                    
                    // Remove interval j
                    free(result[j]);
                    for (int k = j; k < resultSize - 1; k++) {
                        result[k] = result[k + 1];
                    }
                    resultSize--;
                    merged = 1;
                    break;
                }
            }
            if (merged) break;
        }
    }
    
    *returnSize = resultSize;
    return result;
}

int main() {
    // Simple parsing for demonstration
    int intervals[][2] = {{1,3},{2,6},{8,10},{15,18}};
    int* intervalsColSize = (int*)malloc(4 * sizeof(int));
    int** intervalPtrs = (int**)malloc(4 * sizeof(int*));
    
    for (int i = 0; i < 4; i++) {
        intervalPtrs[i] = intervals[i];
        intervalsColSize[i] = 2;
    }
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(intervalPtrs, 4, intervalsColSize, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("[%d,%d]", result[i][0], result[i][1]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops to find overlaps (O(n²)) and potentially n iterations to merge all

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for merging in place

✓ Linear Space

78.0K Views

High Frequency

~15 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler