Definition
- Max-heap by end – process intervals from largest end to smallest so that starts popped for a large end remain valid for smaller ends.
- Max-heap by start – pop all starts >= current end; the last one popped (smallest qualifying start) is the answer.
- Re-offer trick – starts popped but too large for the current end are re-offered because they may serve a smaller end later.
- Original index tracking – each heap entry carries the interval's original index because the result maps original positions.
- Time O(n log n) – each interval is pushed and popped from each heap at most once.
At National Bank of India, each loan has a disbursement window with a start date and an end date. For every loan Rajesh wants the next loan whose window starts on or after the current loan's window ends, so repayments can be chained back to back.
Understanding the Concepts
What is the Next Interval problem?
For each interval in the input, find the interval with the smallest start that is greater than or equal to the current interval's end. If no such interval exists, record -1. The result is an array of original indices.
package com.bank.service;
import java.util.*;
public class NextInterval {
public int[] findRightInterval(int[][] intervals) {
int n = intervals.length;
int[] result = new int[n];
// max-heap by end
PriorityQueue<int[]> endHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
// max-heap by start
PriorityQueue<int[]> startHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
for (int i = 0; i < n; i++) {
endHeap.offer(new int[]{i, intervals[i][1]});
startHeap.offer(new int[]{i, intervals[i][0]});
}
while (!endHeap.isEmpty()) {
int[] top = endHeap.poll();
int idx = top[0], end = top[1];
result[idx] = -1;
int candidateIdx = -1;
while (!startHeap.isEmpty() && startHeap.peek()[1] >= end) {
candidateIdx = startHeap.poll()[0];
}
if (candidateIdx != -1) {
result[idx] = candidateIdx;
startHeap.offer(new int[]{candidateIdx, intervals[candidateIdx][0]});
}
}
return result;
}
public static void main(String[] args) {
int[][] intervals = {{1,2},{2,3},{0,1}};
int[] res = new NextInterval().findRightInterval(intervals);
System.out.println(Arrays.toString(res));
}
}
[1, -1, 0]
Why process ends from largest to smallest?
Processing ends in descending order ensures that a start value popped for a large end might still be valid for a smaller end. If we processed ends from smallest to largest, we would consume start values that might be needed for larger ends later. The largest end needs the largest qualifying start, and any start that was too small for it might work for a smaller end.
package com.bank.service;
public class WhyLargestEndFirst {
// End=10 needs start >= 10
// End=5 needs start >= 5
// If we pop start=8 for end=10 (8 < 10, not valid),
// start=8 is valid for end=5 => re-offer it.
// Processing largest end first ensures we don't discard starts prematurely.
public static void main(String[] args) {
System.out.println("Largest end first: starts popped for large end");
System.out.println("are still valid for smaller ends.");
}
}
How does the re-offer trick work?
When we pop starts from the start-heap looking for ones >= end, the last valid start popped is the smallest qualifying start (because starts are ordered descending). We re-offer this last candidate back into the start-heap because it might also be the answer for a later (smaller) end. Starts that were popped and found too small are not re-offered because they failed the >= end check.
package com.bank.service;
public class ReOfferTrick {
// Start heap (descending): [start=10, idx=0], [start=5, idx=1], [start=2, idx=2]
// Processing end=7:
// Pop start=10: 10 >= 7, candidate=0
// Pop start=5: 5 < 7, stop
// Answer for end=7: idx=0 (start=10)
// Re-offer (idx=0, start=10) because it might serve end=3 later
public static void main(String[] args) {
System.out.println("Last valid pop is the smallest qualifying start.");
System.out.println("Re-offer it for future smaller ends.");
}
}
Can you solve it with binary search instead?
Yes. Sort the intervals by start and for each interval's end, binary search for the smallest start >= end. This gives O(n log n) time and is often simpler. The two-heap approach demonstrates the pattern for interview purposes.
package com.bank.service;
import java.util.*;
public class NextIntervalBinarySearch {
public int[] findRightInterval(int[][] intervals) {
int n = intervals.length;
int[] result = new int[n];
TreeMap<Integer, Integer> startMap = new TreeMap<>();
for (int i = 0; i < n; i++) startMap.put(intervals[i][0], i);
for (int i = 0; i < n; i++) {
Map.Entry<Integer, Integer> entry = startMap.ceilingEntry(intervals[i][1]);
result[i] = entry != null ? entry.getValue() : -1;
}
return result;
}
public static void main(String[] args) {
int[][] intervals = {{1,2},{2,3},{0,1}};
System.out.println(Arrays.toString(
new NextIntervalBinarySearch().findRightInterval(intervals)));
}
}
[1, -1, 0]
How is this different from Maximize Capital?
| Feature | Next Interval | Maximize Capital |
|---|---|---|
| Heaps | max-heap by end + max-heap by start | min-heap by cap + max-heap by profit |
| Goal | find the next starting interval for each | maximise capital by picking K projects |
| Rounds | one per interval (process all ends) | K rounds |
| Re-offer | yes, re-offer the chosen candidate | no |
package com.bank.service;
public class NextIntervalVsCapital {
public static void main(String[] args) {
System.out.println("Both use two heaps, but the mechanics differ.");
System.out.println("Next Interval: re-offer chosen start for future ends.");
System.out.println("Maximize Capital: drain min-heap, pick max profit.");
}
}
What are the edge cases?
Edge cases include a single interval (answer is 0 if start >= end, else -1), intervals where no next interval exists for any, and intervals that are each other's next interval.
package com.bank.service;
import java.util.Arrays;
public class NextIntervalEdgeCases {
public static void main(String[] args) {
NextInterval solver = new NextInterval();
// Single interval
System.out.println("Single: " + Arrays.toString(
solver.findRightInterval(new int[][]{{1,4}})));
// Each is the other's next
System.out.println("Mutual: " + Arrays.toString(
solver.findRightInterval(new int[][]{{1,3},{3,5}})));
}
}
Single: [-1]
Mutual: [1, -1]
What are common mistakes?
The most common mistake is not re-offering the chosen candidate back into the start-heap, which causes it to be unavailable for future smaller ends. Another mistake is forgetting to carry the original index in the heap entries.
Wrong code:
// WRONG: does not re-offer the candidate
int candidateIdx = startHeap.poll()[0];
result[idx] = candidateIdx;
// candidate is lost for future rounds
Correct code:
// CORRECT: re-offer the candidate for future smaller ends
if (candidateIdx != -1) {
result[idx] = candidateIdx;
startHeap.offer(new int[]{candidateIdx, intervals[candidateIdx][0]});
}
What should a senior engineer know?
A senior engineer knows the TreeMap.ceilingEntry approach is simpler and equally O(n log n). They use the two-heap approach when asked specifically to demonstrate the pattern. They also know that this problem is a building block for interval scheduling: finding the next non-overlapping interval is the first step in activity selection.
package com.bank.service;
public class SeniorNextIntervalNotes {
public static void main(String[] args) {
System.out.println("TreeMap.ceilingEntry is simpler for production.");
System.out.println("Two-heap approach demonstrates the pattern.");
System.out.println("Building block for activity selection.");
}
}
Visual Overview
Next Interval: Two Max-Heaps
Intervals: [1,2](idx=0), [2,3](idx=1), [0,1](idx=2)
End-Heap (descending): Start-Heap (descending):
(idx=1, end=3) (idx=1, start=2)
(idx=0, end=2) (idx=0, start=1)
(idx=2, end=1) (idx=2, start=0)
Process end=3 (idx=1):
Pop start=2: 2 < 3? No, 2 < 3 => not valid. Wait:
Actually 2 < 3, so start=2 is not >= end=3.
Hmm, let me re-check: 2 >= 3? No.
No candidate => result[1] = -1
Process end=2 (idx=0):
Pop start=2: 2 >= 2? Yes, candidate=1
Pop start=1: 1 >= 2? No, stop
Re-offer (idx=1, start=2)
result[0] = 1
Process end=1 (idx=2):
Pop start=2: 2 >= 1? Yes, candidate=1
Pop start=1: 1 >= 1? Yes, candidate=0
Pop start=0: 0 >= 1? No, stop
Re-offer (idx=0, start=1)
result[2] = 0
Result: [1, -1, 0]
Key Takeaway
Next Interval asks, for each interval, for the index of the interval with the smallest start >= the current end. The two-heap solution uses a max-heap by end to process the latest-ending interval first, and a max-heap by start to find the smallest qualifying start among all starts >= that end.
The key insight is processing ends from largest to smallest. A start that was too small for a large end may still serve a smaller end later, so the chosen candidate is re-offered into the start-heap. This monotonic argument ensures no valid start is lost.
The simpler alternative is a TreeMap with ceilingEntry: sort starts into a TreeMap and for each end, look up the ceiling (smallest start >= end). Both approaches are O(n log n), and the TreeMap version is more natural for production code.
At National Bank of India, Rajesh uses this to chain loan disbursement windows back to back. For each loan, he finds the next loan whose window starts on or after the current one ends. Explaining the largest-end-first ordering, the re-offer trick, and the TreeMap alternative is what shows an interviewer you understand the two-heap interval matching pattern.
Remember one sentence: process ends from largest to smallest using two max-heaps, and re-offer the chosen start for future smaller ends.
---