Merge Intervals Algorithm: Codes Examples with Visualization
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.
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:
- Start with an empty result list
- 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:
- Sort the intervals by their start times
- Initialize the result list with the first interval
- 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
