Merge Overlapping Subintervals
Problem link: https://leetcode.com/problems/merge-intervals/
Problem Statement
Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of non-overlapping intervals that cover all the intervals in the input.
Input
- intervals: array of intervals [[start, end]]
Output
- Return merged intervals
Example
intervals = [[1,3],[2,6],[8,10],[15,18]]
Explanation
Intervals [1,3] and [2,6] overlap → merge into [1,6]
Final: [[1,6],[8,10],[15,18]]
Brute Force
Intuition
Compare each interval with every other interval and merge if overlapping. Keep repeating until no overlaps remain.
Approach
- Compare all pairs of intervals
- Merge overlapping ones
- Repeat until no overlaps remain
Dry Run
Input: [[1,3],[2,6],[8,10],[15,18]]
Step 1: Compare [1,3] and [2,6] → Overlap → merge → [1,6]
Now list becomes: [[1,6],[8,10],[15,18]]
Step 2: Compare [1,6] with others → No more overlaps
Final: [[1,6],[8,10],[15,18]]
Code (Java)
import java.util.*;
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
boolean merged = true;
while (merged) {
merged = false;
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
int[] a = list.get(i);
int[] b = list.get(j);
if (a[1] >= b[0] && b[1] >= a[0]) {
int start = Math.min(a[0], b[0]);
int end = Math.max(a[1], b[1]);
list.remove(j);
list.remove(i);
list.add(new int[]{start, end});
merged = true;
break;
}
}
if (merged) break;
}
}
return list.toArray(new int[list.size()][]);
}
}
Complexity Analysis
Nested comparisons lead to O(N^2). Repeated merging increases cost.
Optimal Solution
Intuition
If intervals are sorted by start time, overlapping intervals will always be adjacent. So we only need to compare with the last merged interval.
Approach
- Sort intervals by start
- Initialize result with first interval
- For each interval:
- If overlap → merge
- Else → add to result
Dry Run
Input: [[1,3],[2,6],[8,10],[15,18]]
Step 1: Sort (already sorted)
Step 2: Start with [1,3]
Step 3: Compare [1,3] with [2,6] → Overlap → merge → [1,6]
Step 4: Compare [1,6] with [8,10] → No overlap → push [1,6]
Step 5: Compare [8,10] with [15,18] → No overlap → push [8,10]
Final: [[1,6],[8,10],[15,18]]
Code (Java)
import java.util.*;
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> result = new ArrayList<>();
int[] current = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (current[1] >= intervals[i][0]) {
current[1] = Math.max(current[1], intervals[i][1]);
} else {
result.add(current);
current = intervals[i];
}
}
result.add(current);
return result.toArray(new int[result.size()][]);
}
}
Complexity Analysis
Sorting takes O(N log N), merging is O(N).
Quick Revision (Brute Force)
- Compare all pairs
- Merge repeatedly
- O(N^2)
Quick Revision (Optimal)
- Sort + linear scan
- Only check last interval
- O(N log N)