Interval Problems — The Complete Guide

"Sort by start. Merge overlaps. Sweep with a heap. All interval problems reduce to three patterns."

Interval problems cover merging, inserting, covering, scheduling, and sweep-line problems. Learn the three core patterns — sort+merge, sweep line, and DP+binary search — that solve 95% of interval problems.

22 min readscheduling problems →

Problems you can solve with this pattern

8 problems · click any to start solving

All scheduling →

1Merge IntervalsMediumSolve

2Meeting Rooms IIMediumSolve

3Non-overlapping IntervalsMediumSolve

4Jump Game IIMediumSolve

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;
}

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)

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];
}

Medium

Medium

Non-overlapping Intervals

Medium

Medium

Medium

Medium

Minimum Interval to Include Each Query

Hard

Solve

Maximum Profit in Job Scheduling

Hard

Solve

Interval problem decision tree:
1. Need to combine overlapping → sort by START, merge
2. Min rooms / max overlap count → sweep line (events) or two sorted arrays
3. Max non-overlapping count → sort by END, greedy
4. Max weighted non-overlapping → sort by END + DP + binary search
5. Cover a range with min intervals → sort by START, greedy max reach
6. Insert new interval → 3 phases: before / merge overlap / after
7. Queries on intervals → sort both, slide pointer + heap for active intervals

← BFS vs DFS — When to Use Each DP on Trees →