Intervals techniques handle ranges that must be merged, inserted or checked for overlap.
Its core idea:
“Sort intervals first → then merge greedily in one pass.”
Focus on recognizing:
Overlapping ranges / scheduling → sort by start + greedy scan
Core Template: Merge Intervals
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> result = new ArrayList<>();
int[] current = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= current[1]) {
current[1] = Math.max(current[1], intervals[i][1]);
} else {
result.add(current);
current = intervals[i];
}
}
result.add(current);
return result.toArray(new int[result.size()][]);
}def merge(intervals):
intervals.sort(key=lambda x: x[0])
result = []
current = intervals[0]
for start, end in intervals[1:]:
if start <= current[1]:
current[1] = max(current[1], end)
else:
result.append(current)
current = [start, end]
result.append(current)
return resultvector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> result;
auto current = intervals[0];
for (int i = 1; i < (int)intervals.size(); i++) {
if (intervals[i][0] <= current[1]) {
current[1] = max(current[1], intervals[i][1]);
} else {
result.push_back(current);
current = intervals[i];
}
}
result.push_back(current);
return result;
}function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const result = [];
let current = intervals[0];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= current[1]) {
current[1] = Math.max(current[1], intervals[i][1]);
} else {
result.push(current);
current = intervals[i];
}
}
result.push(current);
return result;
}Maintain
current= best merged range so far. Overlap → extend it; gap → save and reset.
Merge = expand until a gap appears. Overlap is transitive when sorted — adjacent comparison is enough.
Pattern 1: Insert Interval
Absorb every overlapping interval, then splice the merged one back in.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Insert Interval
Insert a new interval into an already-sorted list, merging overlaps.
Push all intervals that end before the new start. Then merge every overlapping interval by extending start=min and end=max. Finally push the remaining untouched intervals. Sorted input lets this run as a single O(n) sweep.
1
result = []
2
for iv before overlap: push iv
3
merge all overlapping with new:
4
new.start = min, new.end = max
5
push merged new; push the rest
Watch [1,3] [2,6] [8,10] [9,12] collapse into [1,6] [8,12] — one overlap extends, one gap splits. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Merge Intervals
Given a list of intervals, merge all overlapping intervals into a set of disjoint intervals?
Walk through intervals sorted by start time, merging as you go. On the input, [1,3] and [2,6] overlap (2 <= 3) -> merge to [1,6]. [8,10] starts after 6 -> gap, push [1,6] and start fresh with [8,10]. [9,12] overlaps (9 <= 10) -> merge to [8,12]. Invariant: current holds the merged interval so far; when next.start > current.end, there's a gap. O(n log n) for sort, O(n) merge.
1
sort intervals by start
2
current = intervals[0]
3
for each next interval:
4
if next.start <= current.end: overlap → current.end = max(end)
5
else: push current; current = next
6
push current
Three phases: before the overlap, absorb the overlap, after.
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int i = 0;
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result.add(intervals[i++]);
}
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.add(newInterval);
while (i < intervals.length) {
result.add(intervals[i++]);
}
return result.toArray(new int[result.size()][]);
}def insert(intervals, new_interval):
result = []
i = 0
while i < len(intervals) and intervals[i][1] < new_interval[0]:
result.append(intervals[i])
i += 1
while i < len(intervals) and intervals[i][0] <= new_interval[1]:
new_interval[0] = min(new_interval[0], intervals[i][0])
new_interval[1] = max(new_interval[1], intervals[i][1])
i += 1
result.append(new_interval)
while i < len(intervals):
result.append(intervals[i])
i += 1
return resultvector<vector<int>> insert(vector<vector<int>>& intervals,
vector<int> newInterval) {
vector<vector<int>> result;
int i = 0;
while (i < (int)intervals.size() && intervals[i][1] < newInterval[0])
result.push_back(intervals[i++]);
while (i < (int)intervals.size() && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
i++;
}
result.push_back(newInterval);
while (i < (int)intervals.size())
result.push_back(intervals[i++]);
return result;
}function insert(intervals, newInterval) {
const result = [];
let i = 0;
while (i < intervals.length && intervals[i][1] < newInterval[0])
result.push(intervals[i++]);
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.push(newInterval);
while (i < intervals.length) result.push(intervals[i++]);
return result;
}Insert = merge with controlled placement: skip before, absorb during, copy after.
Pattern 2: Meeting Rooms I (Conflict Detection)
Sort by start; any meeting starting before the previous ends = clash.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Meeting Rooms I (Conflict Check)
Determine whether one person can attend all meetings (no overlaps).
Sort by start time, then check each meeting against the previous one's end. Any start < previous end means a conflict → return false immediately. O(n log n) time, O(1) space.
1
sort by start
2
for i in 1..n-1:
3
if intervals[i].start < intervals[i-1].end:
4
return false // overlap
5
return true
public boolean canAttendMeetings(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 false;
}
}
return true;
}def can_attend_meetings(intervals):
intervals.sort()
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i - 1][1]:
return False
return Truebool canAttendMeetings(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
for (int i = 1; i < (int)intervals.size(); i++)
if (intervals[i][0] < intervals[i - 1][1])
return false;
return true;
}function canAttendMeetings(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i - 1][1]) return false;
}
return true;
}Conflict detection = merge logic reduced to a single adjacency check.
Pattern 3: Meeting Rooms II (Minimum Rooms)
A min-heap of end times decides: reuse a freed room or allocate a new one.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Meeting Rooms II (Min-Heap)
Find the minimum rooms via a min-heap of busy-room end times.
Sort meetings by start. For each, if the earliest ending room has end ≤ the new start it's free — pop and reuse; always push the new end. Peak heap size equals the answer. O(n log n) time; the sweep-line and heap approaches are equivalent.
1
sort by start
2
heap = [] // end times of busy rooms
3
for m in meetings:
4
if heap[0] <= m.start: pop // room freed
5
push m.end
6
answer = peak heap size
A min-heap of end times tracks meetings still in progress:
public int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int[] interval : intervals) {
if (!pq.isEmpty() && pq.peek() <= interval[0]) {
pq.poll();
}
pq.offer(interval[1]);
}
return pq.size();
}import heapq
def min_meeting_rooms(intervals):
intervals.sort()
ends = []
for start, end in intervals:
if ends and ends[0] <= start:
heapq.heappop(ends)
heapq.heappush(ends, end)
return len(ends)int minMeetingRooms(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
priority_queue<int, vector<int>, greater<int>> ends;
for (auto& in : intervals) {
if (!ends.empty() && ends.top() <= in[0])
ends.pop();
ends.push(in[1]);
}
return ends.size();
}// JS has no built-in heap — a sorted array of end times works at
// interview scale.
function minMeetingRooms(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const ends = [];
for (const [start, end] of intervals) {
if (ends.length && ends[0] <= start) ends.shift();
ends.push(end);
ends.sort((a, b) => a - b);
}
return ends.length;
}Heap size = concurrent meetings = rooms needed.
Pattern 4: Sweep Line
+1 on open, −1 on close; the running max is your answer.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Meeting Rooms II (Sweep Line)
Find the minimum number of rooms needed for a set of meetings.
Turn each meeting into +1 (start) and −1 (end) events, with ends processed before starts on a tie so a freed room is reusable. Sweep by time; the peak running sum is the minimum rooms. O(n log n) time, O(n) space.
1
events: (time, ±1), ends before starts
2
sort events by time
3
running += delta
4
rooms = max(rooms, running)
Convert intervals into events (start = +1, end = −1), sort, and run a counter:
events sorted by time → running sum → peak = answerUseful when you need “max simultaneous” without pairing starts to ends.
Common Mistakes
Not sorting first.
Merging order is only guaranteed on sorted starts.
Inverted overlap condition.
Overlap is next.start <= current.end. Using < wrongly separates touching intervals like [1,2] [2,3].
Forgetting the final push.
The last current never hits an “else” branch — always add it after the loop.
Complexity
| Pattern | Time |
|---|---|
| Merge / insert | O(n log n) |
| Meeting rooms II | O(n log n) |
| Sweep line | O(n log n) |
Premium Content
Unlock Intervals and all premium lessons with a subscription.
From ₹199.99/year — See plans