Merge Intervals

Problem Statement

You are given an array of intervals where

intervals[i] = [starti, endi]

Merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals.

Example 1

Input

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

Output

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

Example 2

Input

intervals = [[1,4],[4,5]]

Output

[[1,5]]

Why This Problem Is Important

• Extremely common interview question
• Tests sorting + interval logic
• Used in scheduling, calendar apps, timelines
• Foundation for sweep line and greedy problems

Approaches Overview

Approach 1: Brute Force

Idea

Compare every interval with every other interval and merge overlapping ones repeatedly.

Algorithm

1. For each interval i
2. Compare with all other intervals j
3. If they overlap, merge them
4. Repeat until no more merges possible

Time & Space Complexity

• Time: O(n²)
• Space: O(n)

C Implementation 

#include 
#include 

int overlap(int a[], int b[]) {
    return !(b[0] > a[1] || b[1] < a[0]);
}

void mergeIntervals(int intervals[][2], int n) {
    bool merged = true;

    while (merged) {
        merged = false;
        bool used[n];
        for (int i = 0; i < n; i++) used[i] = false;

        int result[n][2];
        int idx = 0;

        for (int i = 0; i < n; i++) {
            if (used[i]) continue;

            int s = intervals[i][0];
            int e = intervals[i][1];

            for (int j = i + 1; j < n; j++) {
                if (!used[j] && overlap((int[]){s, e}, intervals[j])) {
                    if (intervals[j][0] < s) s = intervals[j][0];
                    if (intervals[j][1] > e) e = intervals[j][1];
                    used[j] = true;
                    merged = true;
                }
            }

            result[idx][0] = s;
            result[idx][1] = e;
            idx++;
        }

        n = idx;
        for (int i = 0; i < n; i++) {
            intervals[i][0] = result[i][0];
            intervals[i][1] = result[i][1];
        }
    }

    printf("Merged Intervals: ");
    for (int i = 0; i < n; i++)
        printf("[%d,%d] ", intervals[i][0], intervals[i][1]);
}

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

Output

Merged Intervals: [1,6] [8,10] [15,18]

 C++ Implementation

#include 
using namespace std;

bool overlap(vector& a, vector& b) {
    return !(b[0] > a[1] || b[1] < a[0]);
}

vector> mergeBruteForce(vector> intervals) {
    bool merged = true;

    while (merged) {
        merged = false;
        vector used(intervals.size(), false);
        vector> result;

        for (int i = 0; i < intervals.size(); i++) {
            if (used[i]) continue;

            int s = intervals[i][0];
            int e = intervals[i][1];

            for (int j = i + 1; j < intervals.size(); j++) {
                if (!used[j] && overlap(intervals[j], vector{s, e})) {
                    s = min(s, intervals[j][0]);
                    e = max(e, intervals[j][1]);
                    used[j] = true;
                    merged = true;
                }
            }
            result.push_back({s, e});
        }
        intervals = result;
    }
    return intervals;
}

int main() {
    vector> intervals = {{1,3},{2,6},{8,10},{15,18}};
    auto res = mergeBruteForce(intervals);

    cout << "Merged Intervals: ";
    for (auto &i : res)
        cout << "[" << i[0] << "," << i[1] << "] ";
}

Output

Merged Intervals: [1,6] [8,10] [15,18]

Java Implementation 

import java.util.*;

public class MergeIntervalsBrute {
    static boolean overlap(int[] a, int[] b) {
        return !(b[0] > a[1] || b[1] < a[0]);
    }

    public static int[][] merge(int[][] intervals) {
        boolean merged = true;

        while (merged) {
            merged = false;
            boolean[] used = new boolean[intervals.length];
            List result = new ArrayList<>();

            for (int i = 0; i < intervals.length; i++) {
                if (used[i]) continue;

                int s = intervals[i][0];
                int e = intervals[i][1];

                for (int j = i + 1; j < intervals.length; j++) {
                    if (!used[j] && overlap(intervals[j], new int[]{s, e})) {
                        s = Math.min(s, intervals[j][0]);
                        e = Math.max(e, intervals[j][1]);
                        used[j] = true;
                        merged = true;
                    }
                }
                result.add(new int[]{s, e});
            }

            intervals = result.toArray(new int[result.size()][]);
        }
        return intervals;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        int[][] res = merge(intervals);

        System.out.print("Merged Intervals: ");
        for (int[] i : res)
            System.out.print("[" + i[0] + "," + i[1] + "] ");
    }
}

Output

Merged Intervals: [1,6] [8,10] [15,18]

Python Implementation

def merge_intervals_bruteforce(intervals):
    merged = True
    while merged:
        merged = False
        result = []
        used = [False] * len(intervals)

        for i in range(len(intervals)):
            if used[i]:
                continue

            s, e = intervals[i]

            for j in range(i + 1, len(intervals)):
                if not used[j]:
                    if not (intervals[j][0] > e or intervals[j][1] < s):
                        s = min(s, intervals[j][0])
                        e = max(e, intervals[j][1])
                        used[j] = True
                        merged = True

            result.append([s, e])

        intervals = result

    return intervals


intervals = [[1,3],[2,6],[8,10],[15,18]]
print("Merged Intervals:", merge_intervals_bruteforce(intervals))

Output

Merged Intervals: [[1, 6], [8, 10], [15, 18]]

JavaScript Implementation 

function overlap(a, b) {
    return !(b[0] > a[1] || b[1] < a[0]);
}

function mergeIntervalsBrute(intervals) {
    let merged = true;

    while (merged) {
        merged = false;
        let used = new Array(intervals.length).fill(false);
        let result = [];

        for (let i = 0; i < intervals.length; i++) {
            if (used[i]) continue;

            let [s, e] = intervals[i];

            for (let j = i + 1; j < intervals.length; j++) {
                if (!used[j] && overlap([s, e], intervals[j])) {
                    s = Math.min(s, intervals[j][0]);
                    e = Math.max(e, intervals[j][1]);
                    used[j] = true;
                    merged = true;
                }
            }
            result.push([s, e]);
        }
        intervals = result;
    }
    return intervals;
}

let intervals = [[1,3],[2,6],[8,10],[15,18]];
console.log("Merged Intervals:", mergeIntervalsBrute(intervals));

Output

Merged Intervals: [ [ 1, 6 ], [ 8, 10 ], [ 15, 18 ] ]

Approach 2: Sorting + Merge

Idea

• Sort intervals by start time
• Merge overlapping intervals in one pass

Algorithm

1. Sort intervals by starting time
2. Initialize result list
3. For each interval:
   • If overlapping with last interval → merge
   • Else → add as new interval

Time & Space Complexity

• Time: O(n log n)
• Space: O(n)

C Implementation 

#include 
#include 

int cmp(const void *a, const void *b) {
    int *i1 = (int *)a;
    int *i2 = (int *)b;
    return i1[0] - i2[0];
}

void mergeIntervals(int intervals[][2], int n) {
    qsort(intervals, n, sizeof(intervals[0]), cmp);

    int start = intervals[0][0];
    int end = intervals[0][1];

    printf("Merged Intervals: ");

    for (int i = 1; i < n; i++) {
        if (intervals[i][0] <= end) {
            if (intervals[i][1] > end)
                end = intervals[i][1];
        } else {
            printf("[%d,%d] ", start, end);
            start = intervals[i][0];
            end = intervals[i][1];
        }
    }
    printf("[%d,%d]", start, end);
}

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

Output

Merged Intervals: [1,6] [8,10] [15,18]

C++ Implementation 

#include 
using namespace std;

vector> mergeIntervals(vector>& intervals) {
    sort(intervals.begin(), intervals.end());

    vector> result;
    result.push_back(intervals[0]);

    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] <= result.back()[1]) {
            result.back()[1] = max(result.back()[1], intervals[i][1]);
        } else {
            result.push_back(intervals[i]);
        }
    }
    return result;
}

int main() {
    vector> intervals = {{1,3},{2,6},{8,10},{15,18}};
    auto res = mergeIntervals(intervals);

    cout << "Merged Intervals: ";
    for (auto &i : res)
        cout << "[" << i[0] << "," << i[1] << "] ";
}

Output

Merged Intervals: [1,6] [8,10] [15,18]

Java Implementation 

import java.util.*;

public class MergeIntervals {
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List result = new ArrayList<>();
        result.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] last = result.get(result.size() - 1);

            if (intervals[i][0] <= last[1]) {
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                result.add(intervals[i]);
            }
        }

        return result.toArray(new int[result.size()][]);
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        int[][] res = merge(intervals);

        System.out.print("Merged Intervals: ");
        for (int[] i : res)
            System.out.print("[" + i[0] + "," + i[1] + "] ");
    }
}

Output

Merged Intervals: [1,6] [8,10] [15,18]

Python Implementation 

def merge_intervals(intervals):
    intervals.sort()
    result = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])

    return result


intervals = [[1,3],[2,6],[8,10],[15,18]]
print("Merged Intervals:", merge_intervals(intervals))

Output

Merged Intervals: [[1, 6], [8, 10], [15, 18]]

JavaScript Implementation 

function mergeIntervals(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);

    let result = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        let last = result[result.length - 1];

        if (intervals[i][0] <= last[1]) {
            last[1] = Math.max(last[1], intervals[i][1]);
        } else {
            result.push(intervals[i]);
        }
    }
    return result;
}

let intervals = [[1,3],[2,6],[8,10],[15,18]];
console.log("Merged Intervals:", mergeIntervals(intervals));

Output

Merged Intervals: [ [ 1, 6 ], [ 8, 10 ], [ 15, 18 ] ]

Next: Approach 3 (In-Place Merge, O(1) space).

Approach 3: In-Place Merge (Space Optimized)

Idea

Reuse the input array itself to store merged intervals.

Algorithm

1. Sort intervals
2. Maintain index k for merged intervals
3. Merge directly into original array

Time & Space Complexity

• Time: O(n log n)
• Space: O(1) (ignoring output)

C Implementation 

#include 
#include 

int cmp(const void *a, const void *b) {
    int *i1 = (int *)a;
    int *i2 = (int *)b;
    return i1[0] - i2[0];
}

void mergeIntervals(int intervals[][2], int n) {
    qsort(intervals, n, sizeof(intervals[0]), cmp);

    int k = 0;

    for (int i = 1; i < n; i++) {
        if (intervals[k][1] >= intervals[i][0]) {
            if (intervals[i][1] > intervals[k][1])
                intervals[k][1] = intervals[i][1];
        } else {
            k++;
            intervals[k][0] = intervals[i][0];
            intervals[k][1] = intervals[i][1];
        }
    }

    printf("Merged Intervals: ");
    for (int i = 0; i <= k; i++)
        printf("[%d,%d] ", intervals[i][0], intervals[i][1]);
}

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

Output

Merged Intervals: [1,6] [8,10] [15,18]

C++ Implementation 

#include 
using namespace std;

vector> mergeInPlace(vector>& intervals) {
    sort(intervals.begin(), intervals.end());

    int k = 0;
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[k][1] >= intervals[i][0]) {
            intervals[k][1] = max(intervals[k][1], intervals[i][1]);
        } else {
            k++;
            intervals[k] = intervals[i];
        }
    }

    intervals.resize(k + 1);
    return intervals;
}

int main() {
    vector> intervals = {{1,3},{2,6},{8,10},{15,18}};
    auto res = mergeInPlace(intervals);

    cout << "Merged Intervals: ";
    for (auto &i : res)
        cout << "[" << i[0] << "," << i[1] << "] ";
}

Output

Merged Intervals: [1,6] [8,10] [15,18]

Java Implementation 

import java.util.*;

public class MergeIntervalsInPlace {
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        int k = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[k][1] >= intervals[i][0]) {
                intervals[k][1] = Math.max(intervals[k][1], intervals[i][1]);
            } else {
                k++;
                intervals[k] = intervals[i];
            }
        }

        return Arrays.copyOf(intervals, k + 1);
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        int[][] res = merge(intervals);

        System.out.print("Merged Intervals: ");
        for (int[] i : res)
            System.out.print("[" + i[0] + "," + i[1] + "] ");
    }
}

Output

Merged Intervals: [1,6] [8,10] [15,18]

Python Implementation 

def merge_intervals_inplace(intervals):
    intervals.sort()
    k = 0

    for i in range(1, len(intervals)):
        if intervals[k][1] >= intervals[i][0]:
            intervals[k][1] = max(intervals[k][1], intervals[i][1])
        else:
            k += 1
            intervals[k] = intervals[i]

    return intervals[:k+1]


intervals = [[1,3],[2,6],[8,10],[15,18]]
print("Merged Intervals:", merge_intervals_inplace(intervals))

Output

Merged Intervals: [[1, 6], [8, 10], [15, 18]]

JavaScript Implementation 

function mergeIntervalsInPlace(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);

    let k = 0;

    for (let i = 1; i < intervals.length; i++) {
        if (intervals[k][1] >= intervals[i][0]) {
            intervals[k][1] = Math.max(intervals[k][1], intervals[i][1]);
        } else {
            k++;
            intervals[k] = intervals[i];
        }
    }

    return intervals.slice(0, k + 1);
}

let intervals = [[1,3],[2,6],[8,10],[15,18]];
console.log("Merged Intervals:", mergeIntervalsInPlace(intervals));

Output

Merged Intervals: [ [ 1, 6 ], [ 8, 10 ], [ 15, 18 ] ]

Summary

• Brute force is for understanding only
• Sorting + merge is interview standard
• In-place merge optimizes space
• Always explain approach 2 in interviews

Next Problem in the Series

Count Reverse Pairs