Merge Intervals Algorithm: Codes Examples with Visualization

Sasank Nasika
Written by
Sasank Nasika
Sasank Nasika
Sasank Nasika

Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.

All articles by
Sasank Nasika
Edited by
Kaustubh Saini
Kaustubh Saini
Kaustubh Saini

Kaustubh Saini writes about software development in a way that’s easy to follow and genuinely helpful. He breaks down complex topics-from AI to the latest in tech-so they actually make sense. His goal is simple: help others learn, stay curious, and keep up with a fast-changing world.

All articles by
Kaustubh Saini
Last updated on
May 14, 2025
In this blog, we'll dive into the "Merge Intervals" algorithm, exploring how to efficiently handle overlapping ranges and merge them into the smallest number of intervals.
Merge Intervals Algorithm: Codes Examples with Visualization

Problem Statement

Given a collection of intervals where each interval consists of a start point and an end point, the task is to merge all overlapping intervals and return a new collection of non-overlapping intervals.

For example, if the input is [[1,3], [2,6], [8,10], [15,18]], the output should be [[1,6], [8,10], [15,18]] because the intervals [1,3] and [2,6] overlap and can be merged into [1,6].

[1 , 3] and [2 , 6] They overlap because 3 ≥ 2, so we merge them into [1,6]

Now [1 ,6] and [8, 10] ,They don't overlap (6 < 8), so we keep them separate and check the next interval [15,18]

[15,18] also don’t overlap with [8,10]


Brute Force Approach

Explanation

The simplest way to tackle this problem is to check each interval against every other interval to see if they overlap. If two intervals overlap, we merge them into a single interval and continue the process.

The brute force approach works like this:

  1. Start with an empty result list
  2. For each interval in the input:
  • Check if it overlaps with any interval in the result list
  • If it overlaps, merge them
  • If not, add the interval to the result list

Two intervals [a,b] and [c,d] overlap if max(a,c) <= min(b,d).

When merging, the new interval is [min(a,c), max(b,d)].

This approach has a time complexity of O(n²) because for each interval, we might need to check all intervals in the result list. The space complexity is O(n) for storing the result.

Code (Python)


def merge_intervals(intervals):
    if not intervals:
        return []

    result = []

    for interval in intervals:
        merged = False

        # Check each interval in the result list
        for i in range(len(result)):
            # Check if current interval overlaps with result[i]
            if max(interval[0], result[i][0]) <= min(interval[1], result[i][1]):
                # Merge overlapping intervals
                result[i] = [min(interval[0], result[i][0]), max(interval[1], result[i][1])]
                merged = True
                break

        # If no overlap found, add the interval to result
        if not merged:
            result.append(interval)

    return result

Code (C++)

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return {};
    }

    vector<vector<int>> result;

    for (const auto& interval : intervals) {
        bool merged = false;

        // Check each interval in the result vector
        for (int i = 0; i < result.size(); i++) {
            // Check if current interval overlaps with result[i]
            if (max(interval[0], result[i][0]) <= min(interval[1], result[i][1])) {
                // Merge overlapping intervals
                result[i][0] = min(interval[0], result[i][0]);
                result[i][1] = max(interval[1], result[i][1]);
                merged = true;
                break;
            }
        }

        // If no overlap found, add the interval to result
        if (!merged) {
            result.push_back(interval);
        }
    }

    return result;
}

Code (Java)

public class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }

        List<int[]> result = new ArrayList<>();

        for (int[] interval : intervals) {
            boolean merged = false;

            // Check each interval in the result list
            for (int i = 0; i < result.size(); i++) {
                int[] existingInterval = result.get(i);

                // Check if current interval overlaps with existingInterval
                if (Math.max(interval[0], existingInterval[0]) <= Math.min(interval[1], existingInterval[1])) {
                    // Merge overlapping intervals
                    existingInterval[0] = Math.min(interval[0], existingInterval[0]);
                    existingInterval[1] = Math.max(interval[1], existingInterval[1]);
                    merged = true;
                    break;
                }
            }

            // If no overlap found, add the interval to result
            if (!merged) {
                result.add(interval);
            }
        }

        // Convert List to array
        int[][] resultArray = new int[result.size()][2];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }

        return resultArray;
    }
}

Optimized Approach

Explanation

The optimized approach sorts the intervals by their start times first. This makes the merging process much simpler because once sorted, we only need to compare each interval with the last interval in our result list.

The steps are:

  1. Sort the intervals by their start times
  2. Initialize the result list with the first interval
  3. For each remaining interval:
  • If it overlaps with the last interval in the result, merge them
  • If not, add it to the result

This approach has a time complexity of O(n log n) due to the sorting step, which is better than the O(n²) of the brute force approach. The space complexity remains O(n).

Lets consider [[1,3], [2,6], [8,10], [15,18]].

Since the array is already sorted,lets start merging,

Initialize current  = [1,3].

i = 1

  • current = [2,6], last = [1,3]
  • current[0] <= last[1] → 2 <= 3 → Overlap!
  • Merge:

    last[1] = max(3,6) = 6

    → result = [[1,6]]

i = 2

  • current = [8,10], last = [1,6]
  • 8 <= 6 → No overlap

    → Append:

    result = [[1,6], [8,10]]

i = 3

  • current = [15,18], last = [8,10]
  • 15 <= 10 → No overlap

    → Append:

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


<visualization-box>

Code (Python)

def merge_intervals(intervals):
    if not intervals:
        return []

    result = []

    for interval in intervals:
        merged = False

        # Check each interval in the result list
        for i in range(len(result)):
            # Check if current interval overlaps with result[i]
            if max(interval[0], result[i][0]) <= min(interval[1], result[i][1]):
                # Merge overlapping intervals
                result[i] = [min(interval[0], result[i][0]), max(interval[1], result[i][1])]
                merged = True
                break

        # If no overlap found, add the interval to result
        if not merged:
            result.append(interval)

    return result

Code (C++)

#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return {};
    }

    vector<vector<int>> result;

    for (const auto& interval : intervals) {
        bool merged = false;

        // Check each interval in the result vector
        for (int i = 0; i < result.size(); i++) {
            if (max(interval[0], result[i][0]) <= min(interval[1], result[i][1])) {
                // Merge overlapping intervals
                result[i][0] = min(interval[0], result[i][0]);
                result[i][1] = max(interval[1], result[i][1]);
                merged = true;
                break;
            }
        }

        if (!merged) {
            result.push_back(interval);
        }
    }

    return result;
}

Code (Java)

import java.util.*;

public class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }

        List<int[]> result = new ArrayList<>();

        for (int[] interval : intervals) {
            boolean merged = false;

            for (int i = 0; i < result.size(); i++) {
                int[] existing = result.get(i);

                if (Math.max(interval[0], existing[0]) <= Math.min(interval[1], existing[1])) {
                    // Merge overlapping intervals
                    existing[0] = Math.min(interval[0], existing[0]);
                    existing[1] = Math.max(interval[1], existing[1]);
                    merged = true;
                    break;
                }
            }

            if (!merged) {
                result.add(interval);
            }
        }

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

Conclusion

The Merge Intervals problem demonstrates how sorting can simplify a solution and improve time complexity.This is a very common technique used in competitive programming By sorting the intervals by start time, we reduced the time complexity from O(n²) to O(n log n).
This problem teaches important concepts:
• How to identify and merge overlapping ranges
• The benefit of preprocessing data (sorting) to simplify logic
• How to reduce time complexity by avoiding unnecessary comparisons

FAQs

TAGS

Arrays
Stop guessing. Start winning.
We’ll show you the most common interview traps — and how to avoid them.
Learn more
Stop guessing. Start winning.
We’ll show you the most common interview traps — and how to avoid them.
Learn more
FAQ Question
Arrow

FAQ Answer

Revolutionizing Interview Preparation with AI

Try it now - It’s free!