DSA-035 · FOCUSED PRACTICE
Merge Intervals
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 3006 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the sorted union of closed intervals by merging every overlapping pair, including intervals that touch at an endpoint.
- Non-null int[][] containing 0–100,000 non-null [start,end] rows, each exactly length 2 with signed int endpoints and start≤end.
- Intervals are closed: [1,2] and [2,3] merge; [1,1] and [2,2] remain separate. Output is sorted by start, pairwise disjoint, and minimal.
- Preserve input rows and their order. Every returned interval is independent of every input row; callers may mutate the output without changing the input.
Examples
Input:
[[1,3],[2,6],[8,10],[15,18]]
Output:[[1,6],[8,10],[15,18]]Only the first two overlap.
Input:
[[1,4],[2,3]]
Output:[[1,4]]A contained interval must not shorten the current end.
Input:
[[1,2],[2,3]]
Output:[[1,3]]A shared endpoint is an overlap under the closed-interval contract.
Before you start
- Closed endpoints and overlap tests
- Deep copying nested arrays and safe comparators
Recognize the structure
Sorting by start creates a frontier: the next interval can interact only with the last merged group. This is union construction, not maximum non-overlapping selection or room allocation, whose greedy states differ.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 100/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
What order makes potential overlap local?
Hint 2
After sorting, which already-merged interval can the next one touch?
Hint 3
Compare with the last end, append on a strict gap, otherwise extend with max.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Repeatedly merge any overlapping pair
Copy rows into mutable groups, find a pair that overlaps, replace it by their union, and restart until no pair overlaps; finally sort groups. On [[1,2],[5,6],[2,5]], merging the first and third group creates [1,5], which then merges with [5,6]. At most n-1 merges occur, each search can inspect O(n²) pairs, giving a conservative O(n³) bound plus final sorting and O(n) storage. It is suitable only for small oracle cases.
Improve the baseline
Sort copies by start
Use Integer.compare, not subtraction. Copy every row because extending an end must not modify caller data.
Keep one open merged group
If the next start exceeds the last end, the previous group is finished. Otherwise the next interval belongs to that group.
Extend with a maximum
Set the current end to max(currentEnd,nextEnd). A nested interval contributes no new coverage and must not shrink the union.
Why it is correct
Initialize
Before scanning, no intervals are represented; the empty result is exactly the union of the empty prefix.
Preserve
The result is a sorted disjoint union of processed intervals. If next.start>last.end, no earlier result interval can overlap it, so append. Otherwise it intersects the last group and replacing that end by their maximum represents exactly the same union plus the new interval.
Finish
All intervals have been represented. Adjacent output groups have a strict gap, so none can be merged further. Coverage is exact and the representation is minimal.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public final class Solution {
public static int[][] merge(int[][] intervals) {
int[][] sorted = Arrays.stream(intervals).map(int[]::clone).toArray(int[][]::new);
Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] interval : sorted) {
if (merged.isEmpty() || interval[0] > merged.getLast()[1]) {
merged.add(interval);
} else {
int[] last = merged.getLast();
last[1] = Math.max(last[1], interval[1]);
}
}
return merged.toArray(int[][]::new);
}
public static int[][] baseline(int[][] intervals) {
List<int[]> groups = new ArrayList<>();
for (int[] interval : intervals) groups.add(interval.clone());
boolean changed;
do {
changed = false;
outer: for (int i = 0; i < groups.size(); i++) {
for (int j = i + 1; j < groups.size(); j++) {
int[] a = groups.get(i), b = groups.get(j);
if (a[0] <= b[1] && b[0] <= a[1]) {
a[0] = Math.min(a[0], b[0]);
a[1] = Math.max(a[1], b[1]);
groups.remove(j);
changed = true;
break outer;
}
}
}
} while (changed);
groups.sort((a, b) -> Integer.compare(a[0], b[0]));
return groups.toArray(int[][]::new);
}
}
Read the meaningful blocks
Deep-copy before sorting
An outer-array clone alone shares mutable rows.
Compare safely
Integer.compare handles extreme endpoints without arithmetic overflow.
Append or extend
The strict start>end test encodes closed endpoints; extension uses max and the returned rows come only from copied data.
Complexity
The sweep is O(n) after O(n log n) sorting. Copying and the result use O(n) storage; object-array sorting may also use O(n) auxiliary references.
Output can contain n intervals. The repeated-pair baseline has conservative O(n³) time and O(n) storage. No method here claims constant extra space while preserving input.
Exact-state walkthroughs
Reveal normal and boundary traces
Nested and touching groups
Input: [[1,4],[2,3],[4,6],[8,8]] · Result: [[1,6],[8,8]]
Step 1 of 6: Deep-copy and sort by start.
Input rows remain unchanged; possible overlap is now local.
Empty at this step.
| Variable | Value |
|---|---|
| sorted | [[1,4],[2,3],[4,6],[8,8]] |
| merged | [] |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Arrays; 3 import java.util.List; 4 5 public final class Solution { 6 public static int[][] merge(int[][] intervals) { 7 int[][] sorted = Arrays.stream(intervals).map(int[]::clone).toArray(int[][]::new); 8 Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0])); 9 List<int[]> merged = new ArrayList<>(); 10 for (int[] interval : sorted) { 11 if (merged.isEmpty() || interval[0] > merged.getLast()[1]) { 12 merged.add(interval); 13 } else { 14 int[] last = merged.getLast(); 15 last[1] = Math.max(last[1], interval[1]); 16 } 17 } 18 return merged.toArray(int[][]::new); 19 } 20 21 public static int[][] baseline(int[][] intervals) { 22 List<int[]> groups = new ArrayList<>(); 23 for (int[] interval : intervals) groups.add(interval.clone()); 24 boolean changed; 25 do { 26 changed = false; 27 outer: for (int i = 0; i < groups.size(); i++) { 28 for (int j = i + 1; j < groups.size(); j++) { 29 int[] a = groups.get(i), b = groups.get(j); 30 if (a[0] <= b[1] && b[0] <= a[1]) { 31 a[0] = Math.min(a[0], b[0]); 32 a[1] = Math.max(a[1], b[1]); 33 groups.remove(j); 34 changed = true; 35 break outer; 36 } 37 } 38 } 39 } while (changed); 40 groups.sort((a, b) -> Integer.compare(a[0], b[0])); 41 return groups.toArray(int[][]::new); 42 } 43 } 44
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Deep-copy and sort by start.
Input rows remain unchanged; possible overlap is now local.
- sorted
[[1,4],[2,3],[4,6],[8,8]]- merged
[]
- A strict gap starts another group.
Merged groups are sorted, disjoint, and cover processed intervals.
- interval
[1,4]- merged
[[1,4]]
- Extend the last overlapping group.
A nested interval never shortens existing coverage.
- interval
[2,3]- merged
[[1,4]]
- Extend the last overlapping group.
A nested interval never shortens existing coverage.
- interval
[4,6]- merged
[[1,6]]
- A strict gap starts another group.
Merged groups are sorted, disjoint, and cover processed intervals.
- interval
[8,8]- merged
[[1,6],[8,8]]
- Return the contract result.
The final state satisfies the requested output contract.
- result
[[1,6],[8,8]]
Separate point intervals
Input: [[2,2],[1,1]] · Result: [[1,1],[2,2]]
Step 1 of 4: Deep-copy and sort by start.
Input rows remain unchanged; possible overlap is now local.
Empty at this step.
| Variable | Value |
|---|---|
| sorted | [[1,1],[2,2]] |
| merged | [] |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Arrays; 3 import java.util.List; 4 5 public final class Solution { 6 public static int[][] merge(int[][] intervals) { 7 int[][] sorted = Arrays.stream(intervals).map(int[]::clone).toArray(int[][]::new); 8 Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0])); 9 List<int[]> merged = new ArrayList<>(); 10 for (int[] interval : sorted) { 11 if (merged.isEmpty() || interval[0] > merged.getLast()[1]) { 12 merged.add(interval); 13 } else { 14 int[] last = merged.getLast(); 15 last[1] = Math.max(last[1], interval[1]); 16 } 17 } 18 return merged.toArray(int[][]::new); 19 } 20 21 public static int[][] baseline(int[][] intervals) { 22 List<int[]> groups = new ArrayList<>(); 23 for (int[] interval : intervals) groups.add(interval.clone()); 24 boolean changed; 25 do { 26 changed = false; 27 outer: for (int i = 0; i < groups.size(); i++) { 28 for (int j = i + 1; j < groups.size(); j++) { 29 int[] a = groups.get(i), b = groups.get(j); 30 if (a[0] <= b[1] && b[0] <= a[1]) { 31 a[0] = Math.min(a[0], b[0]); 32 a[1] = Math.max(a[1], b[1]); 33 groups.remove(j); 34 changed = true; 35 break outer; 36 } 37 } 38 } 39 } while (changed); 40 groups.sort((a, b) -> Integer.compare(a[0], b[0])); 41 return groups.toArray(int[][]::new); 42 } 43 } 44
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Deep-copy and sort by start.
Input rows remain unchanged; possible overlap is now local.
- sorted
[[1,1],[2,2]]- merged
[]
- A strict gap starts another group.
Merged groups are sorted, disjoint, and cover processed intervals.
- interval
[1,1]- merged
[[1,1]]
- A strict gap starts another group.
Merged groups are sorted, disjoint, and cover processed intervals.
- interval
[2,2]- merged
[[1,1],[2,2]]
- Return the contract result.
The final state satisfies the requested output contract.
- result
[[1,1],[2,2]]
Test the contract
Input:
[]
Output:[]No intervals.
Input:
[[2,2]]
Output:[[2,2]]Point interval.
Input:
[[1,1],[2,2]]
Output:[[1,1],[2,2]]Distinct points have a gap.
Input:
[[5,7],[1,3],[3,6]]
Output:[[1,7]]Unsorted transitive overlap.
Common mistakes and counterexamples
Treat touching endpoints as disjoint
Counterexample: [[1,2],[2,3]] must become [[1,3]].
Use next.start>last.end as the disjoint condition.
Assign the next end directly
Counterexample: [[1,10],[2,3]] would incorrectly shrink to [1,3].
Take the maximum end.
Return aliased input rows
Counterexample: Mutating result[0][1] could change the caller’s data.
Deep-copy rows before modifying or returning them.
Follow-ups
Insert one interval into an already merged list.
Copy all intervals before the new start, merge its overlaps, and append the rest. Sorted disjoint input permits O(n) time without sorting again.
Use half-open intervals [start,end).
Endpoint equality no longer means overlap. Specify whether empty intervals are retained and whether merely adjacent coverage should be coalesced; update the contract before changing the inequality.
Intervals arrive online.
Use an ordered map keyed by start, find predecessor/successor overlaps, and merge affected groups. Include the number of removed overlaps in per-operation cost.