Merge Intervals
Mahabharata — Drona's Battle Formations — Consolidating Overlapping Patrol Schedules
यत्र पूर्वं उत्तरं च मिलति तत्र एकम् एव। व्यापिभागान् मिलयित्वा एकं व्यूहं रचयेत्॥
*Where the previous and the next overlap — there they are one. Merge the overlapping sections into a single formation.*
The Story
General Drona was managing patrol schedules for the Kaurava camp perimeter. Each patrol covered a time interval [start, end]. Several patrols overlapped — one ended while another had already started. Drona needed to merge all overlapping patrols into consolidated coverage intervals, eliminating gaps and duplicates.
Patrol schedule: `[[1,3],[2,6],[8,10],[15,18]]`
"Sort by start time," Drona instructed. "Then walk through: if the current interval overlaps with the last one in our result (current.start <= last.end), merge them by extending the end. Otherwise, the current interval is separate — add it."
Tracing: - Sort: already sorted [[1,3],[2,6],[8,10],[15,18]] - Add [1,3] to result - [2,6]: start=2 <= last.end=3 → overlap! Merge: extend end to max(3,6)=6. Result=[[1,6]] - [8,10]: start=8 > last.end=6 → no overlap. Add. Result=[[1,6],[8,10]] - [15,18]: start=15 > 10 → add. Result=[[1,6],[8,10],[15,18]]
Answer: `[[1,6],[8,10],[15,18]]`
"The overlap check is `current.start <= last.end`," Drona noted. "Equal endpoints count as overlap (touching intervals merge). The merged end is `max(last.end, current.end)` — handles full containment too: [1,10] and [2,5] merge to [1,10]."
This is the canonical Merge Intervals technique: sort + single-pass merge.
The Scheduler's First Instinct
Repeatedly find any two overlapping intervals and merge them. O(n²) comparisons per pass, multiple passes needed.
public int[][] mergeBruteForce(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), b = list.get(j);
if (a[0] <= b[1] && b[0] <= a[1]) { // overlap
list.set(i, new int[]{Math.min(a[0],b[0]), Math.max(a[1],b[1])});
list.remove(j); merged = true; break;
}
}
if (merged) break;
}
}
return list.toArray(new int[0][]);
}Drona's Merge Wisdom
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> result = new ArrayList<>();
for (int[] interval : intervals) {
if (result.isEmpty() || result.get(result.size()-1)[1] < interval[0]) {
result.add(interval); // No overlap
} else {
// Merge: extend the end
result.get(result.size()-1)[1] = Math.max(
result.get(result.size()-1)[1], interval[1]);
}
}
return result.toArray(new int[0][]);
}Step-by-Step Walkthrough
intervals=[[1,4],[4,5]] Sort: [[1,4],[4,5]] Add [1,4]. [4,5]: start=4 <= last.end=4 → overlap (touching)! Merge: end=max(4,5)=5. Result: [[1,5]] ✅ (Touching intervals [1,4] and [4,5] merge to [1,5])
Deep Insight
**Why sort by start time?** After sorting, any overlapping interval with the current one must be adjacent in the sorted order (or already merged into the last result). No need to check non-adjacent pairs.
**Full containment:** [1,10] and [2,5] → 2<=10, merge: end=max(10,5)=10. The smaller interval is swallowed.
**Touching intervals ([1,4],[4,5]):** 4<=4 is true → merged. If the problem says touching is NOT an overlap, change `<=` to `<` in the overlap check.
**Time: O(n log n)** dominated by sorting; the merge pass is O(n).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Multiple passes until no overlaps remain |
| Optimal | O(n log n) | O(n) | O(n log n) sort + O(n) single-pass merge |
Pattern Recognition
✅ Merge overlapping intervals ✅ Sort by start time first ✅ Single pass: compare with last merged interval ✅ Merge condition: current.start <= last.end **LeetCode Trigger Phrases:** → "merge all overlapping intervals" → "non-overlapping intervals" after merging → "sort intervals" + merge
Bhagavad Gita 6.29
सर्वभूतस्थमात्मानं सर्वभूतानि चात्मनि। ईक्षते योगयुक्तात्मा सर्वत्र समदर्शनः॥
The yogi who is united in yoga sees the Self in all beings and all beings in the Self, seeing equally everywhere.
Connection: Overlapping intervals, like overlapping souls in the cosmic view, are merged into one unified span when their domains touch. The algorithm sees not separation but connection — where two intervals overlap, they are recognized as one. Like the yogi who sees all beings as expressions of one Self, the merge algorithm sees overlapping time spans as one continuous coverage.