Intervals
Interval problems deal with ranges defined by a start and end point. The key technique is sorting intervals (usually by start time) and then scanning through them to merge, insert, or count overlaps. Interval problems appear frequently in scheduling, calendar, and resource allocation contexts. The sorting step transforms a complex problem into a simple linear scan.
When to Use
- →You need to merge overlapping intervals
- →You need to insert a new interval into a sorted list of non-overlapping intervals
- →You need to find the minimum number of intervals to remove to eliminate all overlaps
- →You need to determine the maximum number of concurrent/overlapping intervals
- →You need to check if a person can attend all meetings (no overlaps)
Approach
Almost all interval problems start with sorting by start time (or sometimes end time). After sorting, scan left to right. For merging, compare each interval with the last one in the result: if they overlap (current start <= previous end), merge by extending the end; otherwise, add the current interval as a new entry.
For finding the minimum rooms (or maximum overlap), use the sweep line technique: create events for each start (+1) and end (-1), sort them, and scan through to find the maximum concurrent count. Alternatively, use two sorted arrays of start and end times with two pointers.
For minimum removals to eliminate overlaps (non-overlapping intervals), sort by end time and greedily keep intervals that don't conflict. This is equivalent to the classic activity selection problem where you maximize the number of non-overlapping intervals.
Code Template
// Merge overlapping intervals
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = merged[merged.length - 1];
if (intervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], intervals[i][1]);
} else {
merged.push(intervals[i]);
}
}
return merged;
}
// Insert interval into non-overlapping sorted list
function insert(intervals, newInterval) {
const result = [];
let i = 0;
// Add all intervals that end before newInterval starts
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result.push(intervals[i++]);
}
// Merge overlapping intervals with newInterval
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 intervals
while (i < intervals.length) result.push(intervals[i++]);
return result;
}
// Minimum meeting rooms (max overlap count)
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, e = 0;
for (let s = 0; s < starts.length; s++) {
if (starts[s] < ends[e]) rooms++;
else e++;
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}