Quick Overview
Sorting by start time means an interval can only overlap the one immediately before it. That turns a pairwise comparison into a single pass, `O(N log N)` overall and dominated by the sort.
An Interval is a pair [start, end] representing a continuous range of time or space. Common problems include calendar scheduling, room booking, and CPU task scheduling.
Almost all interval algorithms start by sorting intervals by their start time: intervals.sort((a, b) => a[0] - b[0]). Once sorted, any overlapping intervals will be adjacent!
Given an array of intervals, merge all overlapping intervals into a unified schedule:
function mergeIntervals(intervals) {
if (intervals.length <= 1) return intervals;
// 1. Sort intervals by start time in ascending order
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const current = intervals[i];
const previous = merged[merged.length - 1];
// Check if current interval overlaps with previous interval:
// Overlap occurs when current.start <= previous.end
if (current[0] <= previous[1]) {
// Merge by extending the previous interval's end time
previous[1] = Math.max(previous[1], current[1]);
} else {
// No overlap: Push current as a new independent interval
merged.push(current);
}
}
return merged;
}
console.log(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]));
// Output: [ [1, 6], [8, 10], [15, 18] ]
[ 1 ─────── 3 ]
[ 2 ──────────── 6 ] <-- Overlaps (2 <= 3) -> Merged: [ 1 ─────── 6 ]
[ 8 ──── 10 ] <-- No overlap (8 > 6)
previous[1] = current[1] breaks when an interval completely encloses another (e.g. [1, 10] and [2, 5]). Always use Math.max(previous[1], current[1]).Use interval sorting for scheduling algorithms. Next, let's explore Bit Manipulation and Bitmasks!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.