Definition
- Two-pointer scan – walk both sorted lists simultaneously with one pointer each; no additional sorting needed.
- Overlap formula – the intersection of intervals a and b is [max(a.start, b.start), min(a.end, b.end)] if max-start <= min-end.
- End-based advancement – advance the pointer of the interval that ends earlier because it is exhausted and cannot overlap anything further.
- Linear time – O(m + n) where m and n are the list lengths; each pointer advances at most through its own list once.
- No mutation – build a fresh result list without modifying the inputs.
At National Bank of India, Rajesh has two sorted timelines: one of windows when an account was eligible for trading and one of windows when the market was open. He needs the windows when both conditions held. He walks both timelines together, taking the slice where they overlap, and steps forward on whichever window closes first.
Understanding the Concepts
What is the Intervals Intersection problem?
The problem gives two lists of closed intervals, each sorted by start and internally non-overlapping. The task is to return the list of intervals where they overlap. This is solved with a two-pointer scan in linear time.
package com.bank.service;
import java.util.*;
public class IntervalsIntersection {
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][]);
}
public static void main(String[] args) {
int[][] a = {{0,2},{5,10},{13,23},{24,25}};
int[][] b = {{1,5},{8,12},{15,24},{25,26}};
int[][] res = new IntervalsIntersection().intervalIntersection(a, b);
for (int[] r : res) System.out.println("[" + r[0] + "," + r[1] + "]");
}
}
[1,2]
[5,5]
[8,10]
[15,23]
[24,24]
[25,25]
Why does the overlap formula work?
Two intervals [a.start, a.end] and [b.start, b.end] overlap if and only if max(a.start, b.start) <= min(a.end, b.end). The intersection starts at the later of the two starts and ends at the earlier of the two ends. If the start is after the end, the intervals do not overlap.
package com.bank.service;
public class OverlapFormula {
public static void main(String[] args) {
// [1, 5] and [3, 8]
int lo = Math.max(1, 3); // 3
int hi = Math.min(5, 8); // 5
System.out.println("Overlap: [" + lo + "," + hi + "] valid=" + (lo <= hi));
// [1, 3] and [5, 8]
lo = Math.max(1, 5); // 5
hi = Math.min(3, 8); // 3
System.out.println("No overlap: lo=" + lo + " hi=" + hi + " valid=" + (lo <= hi));
}
}
Overlap: [3,5] valid=true
No overlap: lo=5 hi=3 valid=false
Why advance based on end, not start?
The interval that ends earlier is fully exhausted: it cannot overlap any later interval in the other list because all later intervals start even further to the right. So we advance its pointer. If we advanced based on the start, we might skip an interval that still has overlapping potential.
package com.bank.service;
public class EndBasedAdvancement {
// a[i] = [1, 5], b[j] = [3, 8]
// a[i] ends at 5, b[j] ends at 8
// a[i] ends first => advance i
// a[i] cannot overlap b[j+1] because b[j+1].start >= 8 > 5
// Wait, that's not right. a[i] cannot overlap anything starting after 5.
// But b[j] still has room (ends at 8), so it might overlap a[i+1].
public static void main(String[] args) {
System.out.println("Advance the pointer of the interval that ends first.");
System.out.println("That interval is exhausted: all future intervals start later.");
System.out.println("The other interval might still overlap the next one.");
}
}
How does the banking trading-window example work?
At National Bank of India, an automated trading account can only place orders when two conditions hold simultaneously: an account eligibility window and a market open session. Both are maintained as sorted non-overlapping lists. The engine needs the exact windows where both overlap.
package com.bank.service;
import java.util.*;
public class TradingWindowService {
record Window(int open, int close) {}
public List<Window> findTradeableWindows(List<Window> eligibility, List<Window> market) {
List<Window> result = new ArrayList<>();
int i = 0, j = 0;
while (i < eligibility.size() && j < market.size()) {
int lo = Math.max(eligibility.get(i).open(), market.get(j).open());
int hi = Math.min(eligibility.get(i).close(), market.get(j).close());
if (lo <= hi) result.add(new Window(lo, hi));
if (eligibility.get(i).close() < market.get(j).close()) i++;
else j++;
}
return result;
}
public static void main(String[] args) {
List<Window> eligibility = List.of(new Window(9, 12), new Window(14, 17));
List<Window> market = List.of(new Window(10, 15), new Window(16, 18));
List<Window> tradeable = new TradingWindowService()
.findTradeableWindows(eligibility, market);
for (Window w : tradeable) {
System.out.println("[" + w.open() + ", " + w.close() + "]");
}
}
}
[10, 12]
[14, 15]
[16, 17]
How is this different from Merge Intervals?
| Feature | Merge Intervals | Interval Intersection |
|---|---|---|
| Input | one unsorted list | two sorted lists |
| Goal | merge overlapping | find overlapping portions |
| Sort needed | yes | no (already sorted) |
| Output | merged intervals | intersection intervals |
| Technique | sort + sweep + extend | two-pointer + max-start/min-end |
package com.bank.service;
public class MergeVsIntersection {
public static void main(String[] args) {
System.out.println("Merge: one list, sort, sweep, extend on overlap.");
System.out.println("Intersection: two lists, two pointers, max-start to min-end.");
}
}
What are the edge cases?
Edge cases include one empty list (no intersections), no overlapping intervals between the two lists, intervals that touch at a single point, and one list entirely contained within the gaps of the other.
package com.bank.service;
public class IntersectionEdgeCases {
public static void main(String[] args) {
IntervalsIntersection solver = new IntervalsIntersection();
// One empty list
int[][] r = solver.intervalIntersection(new int[][]{{1,5}}, new int[][]{});
System.out.println("Empty list: " + r.length + " results");
// Touch at a point
r = solver.intervalIntersection(new int[][]{{1,5}}, new int[][]{{5,10}});
System.out.println("Touch: [" + r[0][0] + "," + r[0][1] + "]");
}
}
Empty list: 0 results
Touch: [5,5]
What are common mistakes?
The most common mistake is advancing the pointer based on the start instead of the end, which skips intervals that still have overlapping potential. Another mistake is using strict less-than for the overlap check (lo < hi), which misses single-point intersections.
Wrong code:
// WRONG: advances based on start, skips potential overlaps
if (a[i][0] < b[j][0]) i++; else j++;
Correct code:
// CORRECT: advances based on end
if (a[i][1] < b[j][1]) i++; else j++;
What should a senior engineer know?
A senior engineer knows that this generalises to intersecting N sorted lists using a min-heap to coordinate the end-advance logic. They also know the time is O(m + n) and the space is O(1) beyond the output. The end-based pointer advancement is the crux of the technique, and it is the same idea that appears in merge-sort's merge step.
package com.bank.service;
public class SeniorIntersectionNotes {
public static void main(String[] args) {
System.out.println("Generalises to N lists with a min-heap.");
System.out.println("O(m + n) time, O(1) extra space.");
System.out.println("End-based advancement is the key correctness detail.");
}
}
Visual Overview
Interval Intersection: Two-Pointer Scan
List A: [0,2] [5,10] [13,23] [24,25]
List B: [1,5] [8,12] [15,24] [25,26]
Step 1: a=[0,2] b=[1,5]
lo=max(0,1)=1 hi=min(2,5)=2 => [1,2]
a ends first (2<5) => advance i
Step 2: a=[5,10] b=[1,5]
lo=max(5,1)=5 hi=min(10,5)=5 => [5,5]
b ends first (5<10) => advance j
Step 3: a=[5,10] b=[8,12]
lo=max(5,8)=8 hi=min(10,12)=10 => [8,10]
a ends first (10<12) => advance i
Step 4: a=[13,23] b=[8,12]
lo=max(13,8)=13 hi=min(23,12)=12 => 13>12, no overlap
b ends first (12<23) => advance j
... continues until one list exhausted
Key Takeaway
The intervals intersection problem takes two sorted, non-overlapping lists and returns the list where they overlap. The solution is a two-pointer scan in O(m + n) time. At each step, compute the potential overlap as the later of the two starts to the earlier of the two ends. If that range is valid (start <= end), it is a real intersection.
The decision that makes the scan work is advancing the pointer of the interval that ends earlier. That interval is exhausted because it cannot overlap any later interval in the other list. Advancing based on the start instead of the end is the most common mistake and causes skipped overlaps.
At National Bank of India, the trading-window service uses this to find the exact windows when both account eligibility and market open-session conditions hold simultaneously. The two-pointer scan computes all tradeable windows in a single linear pass.
The senior-level insight is that this generalises to intersecting N sorted lists using a min-heap for the end-advance coordination. Explaining the max-start/min-end formula, the end-based advancement, and the generalisation to N lists is what tells an interviewer you own this technique.
Remember one sentence: overlap is max-start to min-end, advance the pointer of whichever interval ends first, and you get all intersections in linear time.
---