Definition
- Merge intervals – combine any intervals that overlap or touch into single continuous intervals, producing a minimal non-overlapping set.
- Sort by start – sorting makes overlap detection local; after sorting, any overlapping interval must overlap the most recently merged one.
- Extend current end – when the next interval's start is at or before the current end, merge by taking the maximum of the two ends.
- Max-end rule – taking the maximum handles the case where the next interval is fully contained within the current one.
- Flush final – after the loop, push the last current interval to the result because it is only closed by a gap that may never come.
At the National Bank of India, Rajesh has many maintenance windows on the core system throughout a day, some overlapping. He lines them up by start time and sweeps once: if the next window starts before the current block ends, they merge into one outage period. If there is a gap, he finalises the current block and starts a new one. The finalised blocks are the real outage periods shown to customers.
Understanding the Concepts
What is the Merge Intervals problem?
The problem gives a list of intervals, each with a start and an end, and asks to combine all overlapping intervals into a minimal set of non-overlapping intervals that cover the same ranges. This is one of the most common interval problems in interviews.
package com.bank.service;
import java.util.*;
public class MergeIntervals {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) return intervals;
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
List<int[]> result = new ArrayList<>();
int[] current = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= current[1]) {
// Overlapping: extend current end
current[1] = Math.max(current[1], intervals[i][1]);
} else {
// Gap: close current, start new
result.add(current);
current = intervals[i];
}
}
result.add(current); // flush final
return result.toArray(new int[0][]);
}
public static void main(String[] args) {
int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
int[][] merged = new MergeIntervals().merge(intervals);
for (int[] m : merged) System.out.println("[" + m[0] + "," + m[1] + "]");
}
}
[1,6]
[8,10]
[15,18]
Why is sorting by start the first step?
Sorting makes overlap detection local. Once intervals are ordered by start time, any interval that overlaps an earlier one must overlap the most recently merged interval, because everything is in start order. Without sorting, every interval would need to be compared against all others, giving O(n squared) time.
package com.bank.service;
public class WhySortByStart {
// Unsorted: [8,10], [1,3], [2,6]
// Sorted: [1,3], [2,6], [8,10]
//
// After sorting, [2,6] only needs to compare with [1,3] (previous)
// because if [2,6] overlaps anything, it overlaps the immediate predecessor.
public static void main(String[] args) {
System.out.println("Sorting by start makes overlap detection O(n).");
System.out.println("Without sorting: O(n^2) all-pairs comparison.");
}
}
Why take the maximum of the two ends?
When two intervals overlap, the merged interval's end is the maximum of the two ends, not simply the next interval's end. This matters when the next interval is fully contained within the current one. If you took the next interval's end, you would shrink the current interval.
package com.bank.service;
public class MaxEndRule {
public static void main(String[] args) {
// Current: [1, 10], Next: [2, 5]
// Next is fully contained. End should stay 10, not shrink to 5.
// Math.max(10, 5) = 10 (correct)
System.out.println("[1,10] merge [2,5] => [1," + Math.max(10, 5) + "]");
System.out.println("[1,3] merge [2,6] => [1," + Math.max(3, 6) + "]");
}
}
[1,10] merge [2,5] => [1,10]
[1,3] merge [2,6] => [1,6]
How do you handle the final interval flush?
The loop closes the current interval only when a gap is found. If the loop ends without a gap (the last intervals overlap), the final merged interval is never pushed to the result. The fix is to always push the current interval after the loop ends.
package com.bank.service;
public class FinalFlush {
// WRONG: misses the last interval
// for (int i = 1; i < n; i++) {
// if (overlap) merge;
// else { result.add(current); current = next; }
// }
// return result; // BUG: current never added if last intervals overlap
// CORRECT: add current after loop
// result.add(current); // flushes the final merged interval
public static void main(String[] args) {
System.out.println("Always add current after the loop to avoid off-by-one.");
}
}
Should touching intervals be merged?
Whether intervals that touch (one ends exactly where the next begins) should be merged is a domain decision. For maintenance windows at the bank, touching windows form a continuous outage, so use <= (less-than-or-equal). For booking slots where a customer leaves at 10:00 and the next arrives at 10:00, they are separate, so use < (strict less-than).
package com.bank.service;
public class TouchingPolicy {
public static void main(String[] args) {
// [1,5] and [5,8]
// <= : merge into [1,8] (continuous block)
// < : separate [1,5] and [5,8]
int end = 5, nextStart = 5;
System.out.println("<= merge: " + (nextStart <= end)); // true
System.out.println("< merge: " + (nextStart < end)); // false
}
}
<= merge: true
< merge: false
How is this different from Insert Interval and Interval Intersection?
| Feature | Merge Intervals | Insert Interval | Interval Intersection |
|---|---|---|---|
| Input | unsorted list of intervals | sorted list + one new interval | two sorted lists |
| Goal | merge all overlapping | insert and merge | find overlapping portions |
| Sort needed | yes | no (already sorted) | no (already sorted) |
| Output | minimal merged list | minimal merged list | list of intersections |
package com.bank.service;
public class IntervalFamilyComparison {
public static void main(String[] args) {
System.out.println("Merge: sort + sweep, merge overlapping.");
System.out.println("Insert: sweep sorted list, merge around new interval.");
System.out.println("Intersection: two-pointer, max-start to min-end.");
}
}
What are the edge cases?
Edge cases include a single interval (return it as-is), all intervals overlapping (merge into one), no overlapping intervals (return all), and intervals with zero length where start equals end.
package com.bank.service;
import java.util.Arrays;
import java.util.Comparator;
public class MergeEdgeCases {
public static void main(String[] args) {
MergeIntervals solver = new MergeIntervals();
// Single interval
int[][] r = solver.merge(new int[][]{{1, 5}});
System.out.println("Single: [" + r[0][0] + "," + r[0][1] + "]");
// All overlapping
r = solver.merge(new int[][]{{1,4},{2,5},{3,6}});
System.out.println("All overlap: [" + r[0][0] + "," + r[0][1] + "]");
// No overlapping
r = solver.merge(new int[][]{{1,2},{5,6},{9,10}});
System.out.println("No overlap: " + r.length + " intervals");
}
}
Single: [1,5]
All overlap: [1,6]
No overlap: 3 intervals
What are common mistakes?
The two most common mistakes are forgetting to take the maximum of the ends (using the next end directly, which shrinks on containment) and forgetting to flush the final interval after the loop.
Wrong code:
// WRONG: uses next end directly, shrinks on containment
current[1] = intervals[i][1]; // BUG: should be Math.max
Correct code:
// CORRECT: takes maximum to handle containment
current[1] = Math.max(current[1], intervals[i][1]);
What should a senior engineer know?
A senior engineer knows this is the base template for the entire merge-intervals family. Insert Interval, Interval Intersection, Meeting Rooms, and free-gap computation all build on the sort-and-sweep skeleton. They also know the time is O(n log n) from the sort with a linear merge pass, and the space is O(n) for the result. For timestamps they use Instant.compareTo and for money they use BigDecimal.compareTo.
package com.bank.service;
public class SeniorMergeNotes {
public static void main(String[] args) {
System.out.println("Senior insights:");
System.out.println(" 1. Base template for all interval problems.");
System.out.println(" 2. O(n log n) sort + O(n) sweep.");
System.out.println(" 3. Max-end and final flush are the two correctness traps.");
System.out.println(" 4. Use Instant.compareTo for timestamps, BigDecimal for money.");
}
}
Visual Overview
Merge Intervals: Sort + Sweep
Input: [1,3] [2,6] [8,10] [15,18]
Sorted: [1,3] [2,6] [8,10] [15,18] (already sorted)
Step 1: current = [1,3]
Step 2: [2,6] start=2 <= 3=end => merge, end=max(3,6)=6
current = [1,6]
Step 3: [8,10] start=8 > 6=end => gap!
result: [1,6]
current = [8,10]
Step 4: [15,18] start=15 > 10=end => gap!
result: [1,6], [8,10]
current = [15,18]
Flush: result: [1,6], [8,10], [15,18]
Containment example:
┌──────────────┐
│ [1, 10] │ current
│ ┌──────┐ │
│ │[2, 5]│ │ next (fully contained)
│ └──────┘ │
└──────────────┘
max(10, 5) = 10 => current stays [1, 10]
Key Takeaway
Merging intervals sorts the input by start time and sweeps once, extending the current interval when the next overlaps and starting a new one when there is a gap. Sorting makes overlap detection local: once intervals are in start order, any overlap must involve the most recently merged interval, so the sweep is a single linear pass.
The two correctness traps are the max-end rule and the final flush. When merging, always take the maximum of the current end and the next end, because the next interval might be fully contained and the current end must not shrink. After the loop, always push the current interval to the result, because it is only closed by a gap that may never come.
The touching policy is a domain decision. For maintenance windows at National Bank of India, touching windows form a continuous outage, so Rajesh uses less-than-or-equal for the overlap test. For booking slots where back-to-back use is allowed, strict less-than keeps them separate.
This is the base template for the entire merge-intervals family. Insert Interval, Interval Intersection, Meeting Rooms, and free-gap computation all build on the sort-and-sweep skeleton. Mastering this one unlocks a whole family of interval questions, and a senior engineer recognises it as a pattern rather than a one-off.
Remember one sentence: sort by start, sweep left to right extending the current interval on overlap with max-end, and always flush the final interval after the loop.
---