Merge Intervals
Problem
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 in the input.
Examples
Example 1
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap and merge into [1,6].
Example 2
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Touching intervals (end == next start) count as overlapping.
Constraints
- •
1 <= intervals.length <= 10^4 - •
intervals[i].length == 2 - •
0 <= starti <= endi <= 10^4
Hints
Hint 1
The brute force repeatedly scans for any overlapping pair and merges it, looping until no overlaps remain — correct, but potentially many passes over the data.
Hint 2
If the intervals were processed in START-TIME order, could a merge decision ever need to look further back than the single most recently merged interval?
Hint 3
Sort by start time first (O(n log n), a one-time cost) — this reduces the whole problem to a single linear sweep, comparing each interval only against the last one merged so far.
Solutions
public int[][] mergeBruteForce(int[][] intervals) {
List<int[]> result = new ArrayList<>(Arrays.asList(intervals));
boolean mergedAny = true;
while (mergedAny) {
mergedAny = false;
outer:
for (int i = 0; i < result.size(); i++) {
for (int j = i + 1; j < result.size(); j++) {
int[] a = result.get(i), b = result.get(j);
if (a[0] <= b[1] && b[0] <= a[1]) { // overlap check
result.set(i, new int[]{Math.min(a[0], b[0]), Math.max(a[1], b[1])});
result.remove(j);
mergedAny = true;
break outer;
}
}
}
}
return result.toArray(new int[result.size()][]);
}Time: O(n^3) worst case (repeated O(n^2) scans) · Space: O(n)