Intervals Intersection
Mahabharata — Pandava and Kaurava Patrol Overlap — Finding Shared Territory
द्वयोः सेनयोः यत्र क्षेत्रं साझं भवति। तत् खण्डं ज्ञात्वा नेता युद्धस्थानं निर्णयेत्॥
*Where the territories of two armies overlap — that shared ground the general must know to decide the battle position.*
The Story
Two armies patrol their own sets of non-overlapping intervals: - Pandava patrols A: `[[0,2],[5,10],[13,23],[24,25]]` - Kaurava patrols B: `[[1,5],[8,12],[15,24],[25,26]]`
The contested zones — intervals where BOTH armies patrol simultaneously — are their intersections.
Nakula drew two pointer lines: "Maintain index i into A and j into B. For each pair (A[i], B[j]), compute the intersection: `lo = max(A[i][0], B[j][0])`, `hi = min(A[i][1], B[j][1])`. If lo <= hi, it's a valid intersection — add it."
"Then advance the pointer of the interval that ENDS FIRST (smaller end) — it can no longer intersect with current j or i respectively."
Tracing: - i=0 [0,2], j=0 [1,5]: lo=max(0,1)=1, hi=min(2,5)=2. 1<=2 ✓ add [1,2]. A ends at 2 < 5 → i++ - i=1 [5,10], j=0 [1,5]: lo=5, hi=5. 5<=5 ✓ add [5,5]. B ends at 5 → j++ - i=1 [5,10], j=1 [8,12]: lo=8, hi=10. ✓ add [8,10]. A ends at 10 < 12 → i++ - i=2 [13,23], j=1 [8,12]: lo=13, hi=12. 13>12 → no intersection. B ends → j++ - Continue...
Result: `[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]`
"Two pointers, O(m+n)," Nakula confirmed. The contested zones were mapped with surgical precision.
The Scout's First Instinct
Compare every pair from A and B. For each pair, compute intersection. O(m×n) time.
public int[][] intervalIntersectionBruteForce(int[][] A, int[][] B) {
List<int[]> result = new ArrayList<>();
for (int[] a : A)
for (int[] b : B) {
int lo = Math.max(a[0], b[0]), hi = Math.min(a[1], b[1]);
if (lo <= hi) result.add(new int[]{lo, hi});
}
return result.toArray(new int[0][]);
}Nakula's Two-Pointer Wisdom
public int[][] intervalIntersection(int[][] A, int[][] B) {
List<int[]> result = new ArrayList<>();
int i = 0, j = 0;
while (i < A.length && j < B.length) {
int lo = Math.max(A[i][0], B[j][0]);
int hi = Math.min(A[i][1], B[j][1]);
if (lo <= hi) result.add(new int[]{lo, hi});
if (A[i][1] < B[j][1]) i++; else j++;
}
return result.toArray(new int[0][]);
}Step-by-Step Walkthrough
A=[[1,7]], B=[[3,10]] i=0,j=0: lo=max(1,3)=3, hi=min(7,10)=7. 3<=7 ✓ add [3,7]. A[0][1]=7 < B[0][1]=10 → i++. i=1, done. Result: [[3,7]] ✅
Deep Insight
**Why advance the pointer with smaller end?** The interval with the smaller end value cannot intersect with future intervals of the other list (they start after the current end). So that pointer advances.
**The intersection formula:** `[max(a0,b0), min(a1,b1)]` — start is the later start (both must have started), end is the earlier end (both must still be ongoing).
**No intersection when lo > hi:** The intervals don't overlap at all.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(m×n) | O(m+n) | All pairs compared |
| Optimal | O(m+n) | O(m+n) | Each interval from A and B processed once |
Pattern Recognition
✅ Find intersections of two sorted interval lists ✅ Two pointers, one per list ✅ Advance pointer with smaller endpoint ✅ Intersection = [max(starts), min(ends)] if valid **LeetCode Trigger Phrases:** → "interval list intersections" → "find common intervals between two lists" → "two sorted interval lists" + overlap
Bhagavad Gita 15.16
द्वाविमौ पुरुषौ लोके क्षरश्चाक्षर एव च। क्षरः सर्वाणि भूतानि कूटस्थोऽक्षर उच्यते॥
There are two beings in the world — the perishable and the imperishable. All creatures are perishable; the unchanging is called imperishable.
Connection: Two armies, two interval lists — the intersection is where both simultaneously exist. Like the Gita's description of two cosmic principles that sometimes align, the intersection algorithm finds precisely where two ordered systems overlap. The two-pointer advance mirrors the inevitable passing of time: once one army's patrol ends, it yields to the next, while the intersection of the moment is recorded.