Overlapping Intervals
Mahabharata — The Spy's Check — Detecting If Any Two Patrols Overlap
यत्र एकस्य समाप्तिः अन्यस्य आरम्भात् पूर्वं। तत्र संघर्षः — तस्मात् दोषं पश्येत्॥
*Where one ends before the other begins — all is well. But where one begins before the other ends — there lies the conflict.*
The Story
A simpler version of the merge intervals family: given a set of intervals, check whether ANY two intervals overlap. If any patrol overlaps with any other, there is a scheduling conflict.
Duryodhana asked: "Do any two of our patrols cover the same time?"
His spy sorted the patrol schedules by start time. Then walked through with a single rule: "If intervals[i].start < intervals[i-1].end — conflict detected."
Why does this work? After sorting by start time, any overlapping pair will appear ADJACENT in the sorted order. If intervals[i].start < intervals[i-1].end — the current patrol starts before the previous one ends → they overlap.
If no adjacent pair overlaps (all `intervals[i].start >= intervals[i-1].end`), then no pair in the entire set overlaps.
For `[[1,3],[5,7],[3,5]]`: Sort: [[1,3],[3,5],[5,7]] - intervals[1].start=3 >= intervals[0].end=3 → OK (touching doesn't overlap) - intervals[2].start=5 >= intervals[1].end=5 → OK Return false (no overlap).
For `[[1,4],[2,5],[7,9]]`: Sort: [[1,4],[2,5],[7,9]] - intervals[1].start=2 < intervals[0].end=4 → OVERLAP! Return true.
"A single pass after sorting," the spy confirmed. "O(n log n) total."
The Scheduler's First Instinct
Check every pair. Two intervals [a1,a2] and [b1,b2] overlap if a1 < b2 AND b1 < a2. O(n²).
boolean overlapsBruteForce(int[][] intervals) {
for (int i = 0; i < intervals.length; i++)
for (int j = i+1; j < intervals.length; j++) {
int[] a = intervals[i], b = intervals[j];
if (a[0] < b[1] && b[0] < a[1]) return true;
}
return false;
}The Spy's Sort-and-Check Wisdom
boolean overlaps(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
for (int i = 1; i < intervals.length; i++)
if (intervals[i][0] < intervals[i-1][1]) return true;
return false;
}Step-by-Step Walkthrough
intervals=[[14,16],[1,3],[5,9]] Sort by start: [[1,3],[5,9],[14,16]] i=1: 5 < 3? No. i=2: 14 < 9? No. Return false ✅ (no overlaps)
Deep Insight
**Why adjacent pairs suffice?** After sorting by start, if interval A overlaps with interval C where B is between them (A.start < B.start < C.start), then B must start after A starts. If A and C overlap (C.start < A.end), then B.start < C.start < A.end → B also overlaps with A. So the overlap would be detected at (A,B), which is adjacent.
**Touching vs. overlapping:** `intervals[i][0] < intervals[i-1][1]` (strict less than) means STRICTLY overlapping. Use `<=` to count touching as overlap.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | All pairs |
| Optimal | O(n log n) | O(1) | Sort + linear scan |
Pattern Recognition
✅ Check if any two intervals overlap ✅ Sort by start, check adjacent pairs ✅ Overlap: intervals[i].start < intervals[i-1].end ✅ O(1) extra space **LeetCode Trigger Phrases:** → "check if any intervals overlap" → "can a person attend all meetings?" → "meeting overlap detection"
Bhagavad Gita 15.5
द्वन्द्वैर्विमुक्ताः सुखदुःखसंज्ञैर् गच्छन्त्यमूढाः पदमव्ययं तत्।
Those who are free from the dualities of pleasure and pain go to the imperishable state.
Connection: Two intervals in conflict — two warriors whose paths collide — create the very dualities of overlap and non-overlap. The sorted check resolves this conflict with equanimity: not by exhaustive comparison of all pairs, but by the wise observation that after proper ordering, conflict always reveals itself in adjacency.