Definition
- Existence check – a simple yes/no answer: do any two intervals overlap?
- Sort by start – reduces the all-pairs question to a single linear adjacency scan.
- Adjacent check – after sorting, if current.start < previous.end, they overlap; return true immediately.
- Touching policy – use strict < if touching intervals are non-overlapping, <= if touching counts as overlap.
- Early exit – return true on the first overlap found; no need to process the rest.
At the National Bank of India, Rajesh has a set of booking windows for a shared settlement channel. Two concurrent bookings of the same exclusive resource would be a conflict. He sorts windows by start and checks each against its predecessor. If any starts before the previous ends, he flags a conflict.
Understanding the Concepts
What is the Overlapping Intervals problem?
The problem gives a set of intervals and asks a simple yes/no question: do any two overlap? This is the lightweight existence-check variant of the merge-intervals family. The naive approach compares every pair (O(n squared)), but sorting reduces it to a single linear scan.
package com.bank.service;
import java.util.Arrays;
import java.util.Comparator;
public class OverlappingIntervals {
public boolean hasOverlap(int[][] intervals) {
if (intervals.length <= 1) return false;
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i - 1][1]) {
return true; // overlap found
}
}
return false;
}
public static void main(String[] args) {
int[][] bookings = {{9, 12}, {13, 15}, {11, 14}};
System.out.println("Has overlap: " + new OverlappingIntervals().hasOverlap(bookings));
}
}
Has overlap: true
Why does sorting collapse all-pairs to adjacency?
After sorting by start, any overlap must involve adjacent intervals in the sorted order. If interval A comes before interval B in start order and they overlap, then B starts before A ends, which surfaces when we compare B to its immediate predecessor A. No non-adjacent pair can overlap without the adjacency check also detecting it.
package com.bank.service;
public class WhyAdjacency {
// Sorted: [1,5], [3,7], [10,12]
// [3,7] starts before [1,5] ends (3 < 5) => overlap
// [10,12] starts after [3,7] ends (10 > 7) => no overlap
// No need to check [1,5] vs [10,12] because if they overlapped,
// [3,7] would overlap one of them too (by the sorted start order).
public static void main(String[] args) {
System.out.println("After sorting, overlap surfaces between adjacent pairs.");
}
}
How does the touching policy work?
Whether intervals that touch (one ends exactly where the next begins) count as overlapping depends on the domain. For booking windows where back-to-back use is allowed, use strict less-than. For time ranges where touching means a conflict, use less-than-or-equal.
package com.bank.service;
public class TouchingPolicyDemo {
public static void main(String[] args) {
int prevEnd = 10, curStart = 10;
// Strict < : touching is NOT overlapping
System.out.println("< : overlap? " + (curStart < prevEnd)); // false
// <= : touching IS overlapping
System.out.println("<= : overlap? " + (curStart <= prevEnd)); // true
}
}
< : overlap? false
<= : overlap? true
How is the banking mini-project structured?
At National Bank of India, the settlement scheduler validates that no two booking windows for the same clearing channel overlap. The validator sorts bookings by start and checks adjacent pairs.
package com.bank.service;
import java.util.*;
public class SettlementBookingValidator {
record Booking(int startHour, int endHour, String desk) {}
public boolean hasConflict(List<Booking> bookings) {
bookings.sort(Comparator.comparingInt(Booking::startHour));
for (int i = 1; i < bookings.size(); i++) {
if (bookings.get(i).startHour() < bookings.get(i - 1).endHour()) {
System.out.println("Conflict: " + bookings.get(i - 1).desk()
+ " and " + bookings.get(i).desk());
return true;
}
}
return false;
}
public static void main(String[] args) {
List<Booking> bookings = new ArrayList<>(List.of(
new Booking(9, 12, "DeskA"),
new Booking(11, 14, "DeskB"),
new Booking(15, 17, "DeskC")
));
boolean conflict = new SettlementBookingValidator().hasConflict(bookings);
System.out.println("Has conflict: " + conflict);
}
}
Conflict: DeskA and DeskB
Has conflict: true
How is this different from Merge Intervals?
| Feature | Detect Overlap | Merge Intervals |
|---|---|---|
| Goal | boolean: any overlap? | list of merged intervals |
| Early exit | yes, on first overlap | no, must process all |
| Output | true or false | merged interval list |
| Complexity | same O(n log n) sort | same, but full sweep |
package com.bank.service;
public class DetectVsMerge {
public static void main(String[] args) {
System.out.println("Detect: boolean, early exit on first overlap.");
System.out.println("Merge: full sweep, produces merged list.");
}
}
What are the edge cases?
Edge cases include a single interval (no possible overlap), all intervals identical (overlap), no overlapping intervals, and intervals fully contained within each other.
package com.bank.service;
public class OverlapEdgeCases {
public static void main(String[] args) {
OverlappingIntervals solver = new OverlappingIntervals();
System.out.println("Single: " + solver.hasOverlap(new int[][]{{1,5}}));
System.out.println("Identical: " + solver.hasOverlap(new int[][]{{1,5},{1,5}}));
System.out.println("No overlap: " + solver.hasOverlap(new int[][]{{1,3},{5,7},{9,11}}));
System.out.println("Contained: " + solver.hasOverlap(new int[][]{{1,10},{3,5}}));
}
}
Single: false
Identical: true
No overlap: false
Contained: true
What are common mistakes?
The most common mistake is comparing with the wrong end value. After sorting by start, the previous interval might have a smaller end than the one before it (if a contained interval was sorted between them). For a pure existence check, comparing to the immediate predecessor's end is sufficient because we return on the first clash. For detecting all overlaps, you would need to track the running maximum end.
Wrong code:
// WRONG: not sorted, comparing arbitrary pairs
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (overlap(i, j)) return true; // O(n^2)
Correct code:
// CORRECT: sort + adjacent check, O(n log n)
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
for (int i = 1; i < intervals.length; i++)
if (intervals[i][0] < intervals[i - 1][1]) return true;
What should a senior engineer know?
A senior engineer recognises this as the lightweight warm-up of the merge-intervals family. They know that the sort collapses an all-pairs question into a single adjacency scan, and that the touching policy (strict vs non-strict) is a real domain decision. They also know that the containment case is handled for free: a contained interval starts before its enclosing interval ends.
package com.bank.service;
public class SeniorOverlapNotes {
public static void main(String[] args) {
System.out.println("Lightweight warm-up of merge-intervals family.");
System.out.println("Sort collapses all-pairs O(n^2) to adjacency O(n).");
System.out.println("Touching policy is a domain decision, not a coding detail.");
System.out.println("Containment handled for free by the start < prevEnd check.");
}
}
Visual Overview
Overlapping Intervals: Sort + Adjacent Check
Input: [9,12] [13,15] [11,14]
Sorted: [9,12] [11,14] [13,15]
Check 1: [11,14].start=11 < [9,12].end=12 => OVERLAP!
Return true immediately (early exit).
No overlap example:
Sorted: [1,3] [5,7] [9,11]
Check 1: 5 < 3? No.
Check 2: 9 < 7? No.
Return false.
Containment example:
Sorted: [1,10] [3,5]
Check 1: 3 < 10? Yes => OVERLAP!
(Contained interval is detected for free)
Timeline:
9 10 11 12 13 14 15
|=========| Booking A: [9,12]
|==========| Booking B: [11,14]
Overlap!
Key Takeaway
The overlapping intervals problem asks a simple yes/no question: do any two intervals overlap? The naive all-pairs check is O(n squared), but sorting by start reduces it to a single linear adjacency scan. After sorting, any overlap surfaces between adjacent intervals, because if an earlier-starting interval overlaps a later one, the later one starts before the earlier one ends.
The touching policy is a domain decision. For settlement booking windows where back-to-back use is allowed, use strict less-than. For time ranges where touching is a conflict, use less-than-or-equal. The containment case is handled for free because a contained interval starts before its enclosing interval ends.
At National Bank of India, the settlement scheduler validates that no two booking windows for the same clearing channel overlap. Sorting by start and checking adjacent pairs answers the conflict question in O(n log n) time, keeping booking confirmation fast even when many desks submit windows.
This is the lightweight existence-check cousin of the merge-intervals family. Mastering it as a warm-up problem and connecting it to merge, insert, and intersection shows an interviewer you understand the entire family rather than one isolated problem.
Remember one sentence: sort by start, check if any interval starts before its predecessor ends, and return true on the first overlap.
---