Interval Problems

"Interval union, intersection, overlap, covering, partition, scheduling. Sweep-line, greedy, segment tree."

Deep Dive Tutorial

Interval problems appear in scheduling, calendar apps, genomics, and almost every system design interview. They share a core structure: overlapping vs non-overlapping ranges. Once you sort by start time, almost all interval problems reduce to three patterns: merge, sweep, or DP. The hardest part is recognizing which pattern applies.

Problem type	Pattern	Time
Merge all overlapping intervals	Sort by start, merge greedily	O(n log n)
Insert interval into sorted list	Find overlap range, merge	O(n)
Minimum intervals to cover range	Greedy: sort by start, pick max reach	O(n log n)
Maximum non-overlapping intervals	Sort by END, greedy pick	O(n log n)
Minimum rooms / platforms needed	Sort starts+ends separately, sweep	O(n log n)
Maximum sum of non-overlapping	Sort by end + DP + binary search	O(n log n)
Count overlapping pairs	Coordinate compression + sweep	O(n log n)

Pattern 1: Merge Overlapping Intervals

Merge intervals — O(n log n)

// Sort by start. Merge current into last if they overlap.
function merge(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [intervals[0]];
    for (const [start, end] of intervals.slice(1)) {
        const last = merged.at(-1);
        if (start <= last[1]) last[1] = Math.max(last[1], end); // overlap: extend
        else merged.push([start, end]);                          // gap: new interval
    }
    return merged;
}

// Insert a new interval into a non-overlapping sorted list
function insert(intervals, newInterval) {
    const res = [];
    let i = 0, [ns, ne] = newInterval;
    // Add all intervals that end before new starts
    while (i < intervals.length && intervals[i][1] < ns) res.push(intervals[i++]);
    // Merge all overlapping
    while (i < intervals.length && intervals[i][0] <= ne) {
        ns = Math.min(ns, intervals[i][0]);
        ne = Math.max(ne, intervals[i][1]);
        i++;
    }
    res.push([ns, ne]);
    // Add remaining
    while (i < intervals.length) res.push(intervals[i++]);
    return res;
}

Pattern 2: Sweep Line (Count Overlaps)

key

Sweep line trick: Split each interval into two events: +1 at start, -1 at end. Sort events by time. Running sum = number of active intervals at any point.

Max running sum = maximum overlap at any point.
When running sum drops to 0 = gap between groups of intervals.

Sweep line — max simultaneous overlaps, min meeting rooms

// Minimum meeting rooms = max simultaneous meetings
function minMeetingRooms(intervals) {
    const events = [];
    for (const [s, e] of intervals) {
        events.push([s, 1]);   // meeting starts: +1 room
        events.push([e, -1]);  // meeting ends:   -1 room
    }
    events.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // tie: end before start

    let rooms = 0, maxRooms = 0;
    for (const [, delta] of events) {
        rooms += delta;
        maxRooms = Math.max(maxRooms, rooms);
    }
    return maxRooms;
}

// Alternative: two sorted arrays (cleaner for equal times)
function minMeetingRoomsAlt(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 < intervals.length; i++) {
        while (ends[j] <= starts[i]) { rooms--; j++; }
        rooms++;
        maxRooms = Math.max(maxRooms, rooms);
    }
    return maxRooms;
}

Pattern 3: Interval DP + Binary Search

Weighted job scheduling — O(n log n)

// Find max weight of non-overlapping intervals
function maxNonOverlapWeight(jobs) {
    jobs.sort((a, b) => a[1] - b[1]); // sort by end time
    const n = jobs.length;
    const dp = new Array(n + 1).fill(0);

    for (let i = 0; i < n; i++) {
        const [start, , weight] = jobs[i];
        // Binary search: last job ending <= start of jobs[i]
        let lo = 0, hi = i;
        while (lo < hi) {
            const mid = (lo + hi + 1) >> 1;
            if (jobs[mid - 1][1] <= start) lo = mid;
            else hi = mid - 1;
        }
        dp[i + 1] = Math.max(dp[i], dp[lo] + weight);
    }
    return dp[n];
}