Intervals are the most predictable pattern on the sheet: nearly every question is "sort by start, then walk the list once", and the two that are not are "sort, then use a heap" or "sort the endpoints instead". Knowing which of those three you are in is the whole job.
The idea
Sorting by start time buys you one guarantee: when you reach interval i, every interval
that could overlap it has already been seen. So a single pass, holding one "current"
interval, is enough — you never need to look ahead.
Two sorted intervals a and b overlap when b.start <= a.end. That is the only
comparison in the pattern.
def merge(intervals):
intervals.sort(key=lambda x: x[0])
out = [intervals[0]]
for start, end in intervals[1:]:
if start <= out[-1][1]: # overlaps the one we are building
out[-1][1] = max(out[-1][1], end)
else:
out.append([start, end])
return outint[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
List<int[]> out = new ArrayList<>();
out.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] last = out.get(out.size() - 1);
if (intervals[i][0] <= last[1]) { // overlaps
last[1] = Math.max(last[1], intervals[i][1]); // max, not assign
} else {
out.add(intervals[i]);
}
}
return out.toArray(new int[0][]);
}vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> out{intervals[0]};
for (size_t i = 1; i < intervals.size(); i++) {
if (intervals[i][0] <= out.back()[1]) { // overlaps
out.back()[1] = max(out.back()[1], intervals[i][1]);
} else {
out.push_back(intervals[i]);
}
}
return out;
}function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const out = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = out[out.length - 1];
if (intervals[i][0] <= last[1]) { // overlaps
last[1] = Math.max(last[1], intervals[i][1]); // max, not assign
} else {
out.push(intervals[i]);
}
}
return out;
}The max matters. [1, 10] followed by [2, 3] must stay [1, 10]; assigning end
directly shrinks it and is the classic bug here.
The three shapes
1. Merge or insert — sort by start, one pass. Merge Intervals, Insert Interval.
Insert Interval is the same walk with the list already sorted: emit everything ending before the new interval, absorb everything overlapping it, emit the rest.
2. Keep the most — sort by *end*, count greedily. Non-overlapping Intervals and
Minimum Number of Arrows both ask how many intervals to remove or how few points hit them all. Sorting by end and always keeping the interval that finishes earliest is optimal, because finishing earliest leaves the most room for everything after it. This is the classic activity-selection exchange argument and it is worth being able to state.
def erase_overlap_intervals(intervals):
intervals.sort(key=lambda x: x[1]) # by END
kept_end = float("-inf")
removed = 0
for start, end in intervals:
if start >= kept_end:
kept_end = end # keep it
else:
removed += 1 # drop the one that ends later
return removedint eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1])); // by END
int keptEnd = Integer.MIN_VALUE, removed = 0;
for (int[] interval : intervals) {
if (interval[0] >= keptEnd) {
keptEnd = interval[1]; // keep it
} else {
removed++; // drop the one that ends later
}
}
return removed;
}int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(),
[](const auto& a, const auto& b) { return a[1] < b[1]; }); // by END
int keptEnd = INT_MIN, removed = 0;
for (const auto& iv : intervals) {
if (iv[0] >= keptEnd) keptEnd = iv[1]; // keep it
else removed++; // drop the later-ending one
}
return removed;
}function eraseOverlapIntervals(intervals) {
intervals.sort((a, b) => a[1] - b[1]); // by END
let keptEnd = -Infinity, removed = 0;
for (const [start, end] of intervals) {
if (start >= keptEnd) keptEnd = end; // keep it
else removed++; // drop the later-ending one
}
return removed;
}3. Count concurrency — min-heap or sweep line. Meeting Rooms II asks for the maximum
number of intervals live at once.
import heapq
def min_meeting_rooms(intervals):
intervals.sort(key=lambda x: x[0])
ends = [] # min-heap of end times, one per room
for start, end in intervals:
if ends and ends[0] <= start:
heapq.heappop(ends) # a room freed up
heapq.heappush(ends, end)
return len(ends)int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
PriorityQueue<Integer> ends = new PriorityQueue<>(); // min-heap of end times
for (int[] interval : intervals) {
if (!ends.isEmpty() && ends.peek() <= interval[0]) {
ends.poll(); // a room freed up
}
ends.offer(interval[1]);
}
return ends.size();
}int minMeetingRooms(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
priority_queue<int, vector<int>, greater<int>> ends; // min-heap
for (const auto& iv : intervals) {
if (!ends.empty() && ends.top() <= iv[0]) {
ends.pop(); // a room freed up
}
ends.push(iv[1]);
}
return (int)ends.size();
}function minMeetingRooms(intervals) {
// No built-in heap in JS. With one meeting per room the sweep-line form is
// simpler and equally O(n log n): sort starts and ends separately.
const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
let rooms = 0, best = 0, e = 0;
for (const start of starts) {
while (e < ends.length && ends[e] <= start) { rooms--; e++; }
rooms++;
best = Math.max(best, rooms);
}
return best;
}The heap's root is the soonest a room frees up, which is the only end time worth checking.
The sweep-line alternative is often cleaner: split each interval into a +1 at its start
and a -1 at its end, sort all the events, and track the running maximum. Ties matter —
process the -1 before the +1 at the same timestamp if a meeting ending at 10 lets
another start at 10, which is usually the intended reading.
Complexity
O(n log n) everywhere, dominated by the sort. The pass afterwards is O(n), and the heap variant is O(n log n) with O(n) worst-case space.
Mistakes that cost the round
- Sorting by the wrong key. Merge sorts by start; the keep-the-most variants sort by
end. Using start for the greedy version produces plausible wrong answers.
- Assigning instead of maxing the end when merging a fully contained interval.
- Getting boundary semantics wrong. Is
[1, 2]and[2, 3]an overlap? Ask. For
meeting rooms it is not; for merging ranges it usually is. State your assumption.
- Mutating the input list while iterating it, in the insert variant.
What to drill
- Merge Intervals — the base case.
- Insert Interval — the same walk without re-sorting.
- Non-overlapping Intervals — sort by end, greedy keep.
- Minimum Number of Arrows to Burst Balloons — the same greedy, phrased backwards.
- Meeting Rooms II — the heap or sweep-line counting variant.
- My Calendar I — the same overlap test against a running set of bookings.
All on the 22 DSA Patterns sheet.
Frequently asked
Should I sort intervals by start or by end?
By start when you are merging or inserting — it guarantees every interval that could overlap the current one has already been seen. By end when you are greedily keeping as many non-overlapping intervals as possible, because the one that finishes earliest leaves the most room for everything after it.
How do I find the minimum number of meeting rooms?
Sort by start and keep a min-heap of end times. For each meeting, pop the heap root if that room has already freed up, then push the new end time. The heap's final size is the maximum concurrency. A sweep line over +1/−1 events at each endpoint gives the same answer.
Do intervals that touch at an endpoint count as overlapping?
It depends on the problem and it is worth asking. Merging ranges usually treats [1,2] and [2,3] as overlapping; meeting rooms usually does not, since a room freed at 10 can host a meeting starting at 10. In a sweep line this is decided by whether −1 events sort before +1 events at the same timestamp.