Definition
- Merge intervals – combine overlapping or touching intervals into a minimal non-overlapping set covering the same ranges.
- Sort by start – ensures overlap detection is local; only compare with the most recently merged interval.
- Max-end rule – when merging, take Math.max(currentEnd, nextEnd) so a fully contained interval does not shrink the current one.
- Gap detection – when the next start exceeds the current end, close the current interval and start a new one.
- Final flush – always add the last current interval after the loop to avoid the off-by-one bug.
At the National Bank of India, Rajesh consolidates account-lock windows. Some locks overlap when multiple operations run concurrently. He sorts locks by start time and sweeps once, merging overlapping windows into the true locked periods that the regulator needs for audit reports.
Understanding the Concepts
What is the Merge Intervals problem?
The problem gives a list of intervals, each with a start and end, and asks to collapse all overlapping ones into a minimal set of non-overlapping intervals that cover the same ranges. This is the foundational problem of the merge-intervals pattern.
package com.bank.service;
import java.util.*;
public class MergeIntervalsService {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) return intervals;
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
List<int[]> merged = new ArrayList<>();
int[] current = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= current[1]) {
current[1] = Math.max(current[1], intervals[i][1]);
} else {
merged.add(current);
current = intervals[i];
}
}
merged.add(current);
return merged.toArray(new int[0][]);
}
public static void main(String[] args) {
int[][] locks = {{9,12},{11,13},{14,16},{15,18},{20,22}};
int[][] result = new MergeIntervalsService().merge(locks);
System.out.println("Merged lock windows:");
for (int[] r : result) System.out.println(" [" + r[0] + ", " + r[1] + "]");
}
}
Merged lock windows:
[9, 13]
[14, 18]
[20, 22]
Why does sorting by start make overlap detection local?
Once intervals are in start order, any interval that overlaps the current merged interval must be its immediate successor or a later one that also overlaps. More importantly, if the next interval does not overlap the current one, no later interval can either (because all later intervals have even larger starts). So we only compare each interval to the single current merged interval.
package com.bank.service;
public class LocalOverlapExplanation {
// Sorted: [1,3] [2,6] [8,10]
// [2,6] overlaps [1,3] because 2 <= 3
// [8,10] does NOT overlap [1,6] because 8 > 6
// Since 8 > 6, no later interval can overlap [1,6] either
// (all later starts >= 8 > 6)
public static void main(String[] args) {
System.out.println("After sorting, if next.start > current.end,");
System.out.println("all subsequent starts are even larger => no overlap.");
}
}
How do you handle the max-end rule for containment?
When merging two overlapping intervals, the merged end is Math.max(currentEnd, nextEnd). This handles the case where the next interval is fully contained within the current one. Without max, you would shrink the current interval.
package com.bank.service;
public class MaxEndContainment {
public static void main(String[] args) {
// Current: [1, 10], Next: [3, 5] (fully contained)
// WRONG: current[1] = 5 (shrank from 10 to 5)
// CORRECT: current[1] = Math.max(10, 5) = 10
int currentEnd = 10;
int nextEnd = 5;
System.out.println("Wrong: " + nextEnd);
System.out.println("Correct: " + Math.max(currentEnd, nextEnd));
}
}
Wrong: 5
Correct: 10
How do you build a complete banking mini-project?
At National Bank of India, the account-lock service records when exclusive locks are held on an account. Multiple operations can lock the same account at overlapping times. The regulator needs the actual total time an account was under any lock, so the service merges overlapping windows.
package com.bank.service;
import java.util.*;
public class AccountLockMerger {
record LockWindow(int startHour, int endHour) {}
public List<LockWindow> mergeLocks(List<LockWindow> windows) {
if (windows.size() <= 1) return windows;
windows.sort(Comparator.comparingInt(LockWindow::startHour));
List<LockWindow> merged = new ArrayList<>();
int curStart = windows.get(0).startHour();
int curEnd = windows.get(0).endHour();
for (int i = 1; i < windows.size(); i++) {
LockWindow w = windows.get(i);
if (w.startHour() <= curEnd) {
curEnd = Math.max(curEnd, w.endHour());
} else {
merged.add(new LockWindow(curStart, curEnd));
curStart = w.startHour();
curEnd = w.endHour();
}
}
merged.add(new LockWindow(curStart, curEnd));
return merged;
}
public static void main(String[] args) {
List<LockWindow> windows = List.of(
new LockWindow(9, 11), new LockWindow(10, 13),
new LockWindow(15, 17), new LockWindow(16, 19)
);
List<LockWindow> merged = new AccountLockMerger().mergeLocks(new ArrayList<>(windows));
System.out.println("Merged locks:");
for (LockWindow w : merged) {
System.out.println(" [" + w.startHour() + ", " + w.endHour() + "]");
}
}
}
Merged locks:
[9, 13]
[15, 19]
How is this different from the overlap-detection variant?
| Feature | Merge Intervals | Detect Any Overlap |
|---|---|---|
| Goal | produce merged list | boolean: any overlap? |
| Output | list of merged intervals | true or false |
| Early exit | no, must process all | yes, on first overlap |
| Post-sort work | extend and flush | one adjacent check |
package com.bank.service;
public class MergeVsDetect {
public static void main(String[] args) {
System.out.println("Merge: produces merged list, processes all intervals.");
System.out.println("Detect: returns boolean, exits on first overlap.");
}
}
What are the edge cases?
Edge cases include a single interval, all intervals identical, intervals already non-overlapping, and an interval of zero length (start equals end).
package com.bank.service;
import java.util.Arrays;
import java.util.Comparator;
public class MergeEdgeCasesDemo {
public static void main(String[] args) {
MergeIntervalsService solver = new MergeIntervalsService();
// All identical
int[][] r = solver.merge(new int[][]{{5,10},{5,10},{5,10}});
System.out.println("All identical: [" + r[0][0] + "," + r[0][1] + "]");
// Zero-length interval
r = solver.merge(new int[][]{{1,1},{2,2}});
System.out.println("Zero-length: " + r.length + " intervals");
}
}
All identical: [5,10]
Zero-length: 2 intervals
What are common mistakes?
The two correctness traps are forgetting Math.max on the end (shrinks on containment) and forgetting to add the final interval after the loop.
Wrong code:
// WRONG: shrinks on containment
current[1] = intervals[i][1];
// WRONG: forgets final flush
// (no result.add(current) after loop)
Correct code:
// CORRECT: max-end and final flush
current[1] = Math.max(current[1], intervals[i][1]);
// ... after loop:
result.add(current);
What should a senior engineer know?
A senior engineer knows this is the foundation of the interval-problems family. They use Instant.compareTo for real timestamps and BigDecimal.compareTo for monetary ranges. They also know the sort is the bottleneck at O(n log n) and the sweep is O(n), and that the space is O(n) for the result or O(1) extra if sorting in place.
package com.bank.service;
public class SeniorMergeIntervalNotes {
public static void main(String[] args) {
System.out.println("Foundation of all interval problems.");
System.out.println("O(n log n) sort + O(n) sweep.");
System.out.println("Use Instant.compareTo for timestamps.");
System.out.println("Two traps: max-end rule, final flush.");
}
}
Visual Overview
Merge Intervals: Sort + Sweep
Input locks: [9,11] [10,13] [15,17] [16,19]
Sorted: [9,11] [10,13] [15,17] [16,19]
current = [9,11]
[10,13]: 10 <= 11 => merge, end=max(11,13)=13
current = [9,13]
[15,17]: 15 > 13 => gap!
result: [9,13]
current = [15,17]
[16,19]: 16 <= 17 => merge, end=max(17,19)=19
current = [15,19]
Flush: result: [9,13], [15,19]
Timeline:
9 10 11 12 13 14 15 16 17 18 19
|=========| Lock 1: [9,11]
|===========| Lock 2: [10,13]
|=========| Lock 3: [15,17]
|===========| Lock 4: [16,19]
|=================| Merged: [9,13]
|=================| Merged: [15,19]
Key Takeaway
The merge intervals problem sorts intervals by start and sweeps once, extending the current interval when the next overlaps and starting a new one when there is a gap. Sorting is the enabling move: once intervals are in start order, overlap detection becomes local because any overlap must involve the most recently merged interval.
The two correctness traps are the max-end rule and the final flush. When merging, take Math.max 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 add the last current interval to the result, because it is only closed by a gap that may never come.
At National Bank of India, the account-lock service merges overlapping lock windows to give the regulator the actual total time an account was under any exclusive lock. Sorting the windows by start and sweeping once collapses all overlaps into the minimal set of distinct locked periods, keeping audit-report generation fast even for busy accounts.
This is the foundational problem of the interval-problems family. Insert Interval, Interval Intersection, Meeting Rooms, and free-gap computation all build on this sort-and-sweep skeleton. A senior engineer recognises it as a reusable pattern and knows to use Instant.compareTo for real timestamps and BigDecimal.compareTo for monetary ranges.
Remember one sentence: sort by start, sweep with max-end to handle containment, flush the final interval, and you have the minimal merged set.
---