Merge, insert, and count overlapping intervals using sorting and greedy strategies.
Interval problems deal with ranges [start, end]. The key insight is to sort intervals by start time. Once sorted, overlapping intervals are always adjacent and can be merged in one linear pass. Counting overlaps uses a sweep line or sorting both start and end arrays.
O(n log n) for sorting, O(n) for sweep
O(n) for output
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this as the default first step for many interval problems
Once intervals are ordered by start, any overlap that matters will appear next to the current interval. This converts a messy global problem into a clean left-to-right sweep.
Problem Merge Intervals. Sort all intervals by start so you can compare each interval only with the latest merged interval.
// Sort by start time — foundation for interval problems
function sortByStart(intervals) {
return intervals.slice().sort((a, b) => a[0] - b[0]);
}
// After sorting, overlapping intervals are always adjacent
// Example: [[3,5],[1,4],[6,9]] -> [[1,4],[3,5],[6,9]]Use this when you need to combine touching or overlapping intervals into larger blocks
Keep the last merged interval and either extend it or start a new one depending on overlap. This is the core interval pattern.
Problem Merge Intervals. If the next interval starts before the current merged interval ends, update the end to the maximum of both ends.
// Merge overlapping intervals
function mergeIntervals(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const result = [];
for (const interval of intervals) {
if (!result.length || interval[0] > result[result.length-1][1])
result.push([...interval]);
else
result[result.length-1][1] = Math.max(result[result.length-1][1], interval[1]);
}
return result;
}Use this when the goal is to select the maximum number of non-overlapping intervals or remove the minimum number of overlaps
Sorting by end time leaves as much room as possible for future intervals, which is why the greedy choice works. This pattern is one of the clearest examples of interval greediness.
Problem Non-overlapping Intervals. Sort by end time and always keep the interval that finishes earliest.
// Greedy by end time — Non-overlapping Intervals (min removals)
function eraseOverlapIntervals(intervals) {
intervals.sort((a, b) => a[1] - b[1]); // sort by END time
let count = 0, end = intervals[0][1];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] < end) count++; // overlap, remove current
else end = intervals[i][1]; // no overlap, update end
}
return count;
}Use this when you need to know how many intervals are active at the same time instead of merging them into one result
By sorting start times and end times separately, you can sweep through the timeline and track how many intervals overlap right now. This is very common in meeting room problems.
Problem Meeting Rooms II. Increase rooms when a meeting starts before the earliest current end; otherwise reuse a finished room.
// Separate start/end sweeps — Meeting Rooms II
function minMeetingRooms(intervals) {
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, maxRooms = 0, j = 0;
for (let i = 0; i < starts.length; i++) {
if (starts[i] < ends[j]) { rooms++; maxRooms = Math.max(maxRooms, rooms); }
else { rooms--; j++; }
}
return maxRooms;
}Use this when one new interval must be added into an already sorted interval list
Instead of rebuilding everything blindly, first append all intervals that end before the new interval starts, then merge overlaps, then append the rest. This pattern keeps the logic linear.
Problem Insert Interval. Push all non-overlapping left intervals, merge all overlapping middle intervals, and then append the remaining right intervals.
// Insert then merge — Insert Interval
function insert(intervals, newInterval) {
const result = [];
let i = 0;
// Add all non-overlapping left intervals
while (i < intervals.length && intervals[i][1] < newInterval[0])
result.push(intervals[i++]);
// Merge all overlapping intervals
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);
// Add remaining right intervals
while (i < intervals.length) result.push(intervals[i++]);
return result;
}Use this when the problem is about coverage, active counts, or timeline transitions rather than just merging ranges
Convert each interval into start and end events, sort the events, and sweep through them in time order while updating state. This generalizes many interval problems beyond simple overlap merging.
Problem Maximum Overlap Count. Add +1 at each start and -1 at each end, sort events, and track the running active interval count.
// Event-based sweep line — Maximum Overlap Count
function maxOverlap(intervals) {
const events = [];
for (const [start, end] of intervals) {
events.push([start, 1]);
events.push([end, -1]);
}
events.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
let active = 0, best = 0;
for (const [, delta] of events) {
active += delta;
best = Math.max(best, active);
}
return best;
}