Intervals

Interval problems give you pairs [start, end] representing ranges and ask you to merge, insert, or remove them — the key insight is almost always to sort by start or end time first, then sweep linearly.

• Replaces brute-force O(n²) overlap checks with O(n log n) by sorting once then doing one greedy pass
• Four modes: merge overlapping intervals, insert a new interval into a sorted list, remove minimum to make non-overlapping, find free gaps within a window
• Reach for it when the problem involves merging ranges, inserting a range, or minimizing overlapping removals

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of interval patterns.

Practice Tips

How to Identify an Interval Problem

• Input is a list of [start, end] pairs representing ranges, meetings, or bookings
• Problem asks to merge, count, insert, or minimize removal of overlapping ranges
• Phrases like "meeting rooms", "overlapping intervals", "insert and merge", "remove minimum to make non-overlapping"

Intervals vs. Other Techniques

Interview Approach

1. Clarify: does "touching" count as overlapping? ([1,4],[4,5] — usually yes)
2. Decide sort key: sort by start for merge/insert style, sort by end for greedy removal
3. For merge: one pass with a result list — extend the last interval's end on overlap
4. For insert: three-phase scan — before / overlapping / after — no re-sorting needed
5. For minimum removal: sort by end; keep intervals that end earliest; count every skip as a removal

4 Main Patterns

Pattern 1: Sort by Start + Merge

Copy// Sort by start time; if current starts after last ends → add; else extend last end
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> result = new ArrayList<>();

for (int[] iv : intervals) {
    if (result.isEmpty() || result.get(result.size()-1)[1] < iv[0]) {
        result.add(iv);  // no overlap
    } else {
        result.get(result.size()-1)[1] = Math.max(result.get(result.size()-1)[1], iv[1]);  // merge
    }
}

Pattern 2: Three-Phase Scan (Insert into Sorted)

Copy// Phase 1: intervals ending before new starts → add as-is
// Phase 2: intervals overlapping with new → expand new interval's bounds
// Phase 3: remaining intervals → add as-is
int i = 0, n = intervals.length;

while (i < n && intervals[i][1] < newInterval[0]) {
    result.add(intervals[i]);
    i++;
}
while (i < n && intervals[i][0] <= newInterval[1]) {
    int curStart = intervals[i][0];
    int curEnd   = intervals[i][1];
    newInterval[0] = Math.min(newInterval[0], curStart);
    newInterval[1] = Math.max(newInterval[1], curEnd);
    i++;
}
result.add(newInterval);
while (i < n) {
    result.add(intervals[i]);
    i++;
}

Pattern 3: Sort by End + Greedy Keep

Copy// Sort by end; always keep the interval that ends earliest
// When two overlap, remove the current one (it ends later by definition after sorting)
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int removed = 0, lastKeptEnd = Integer.MIN_VALUE;
for (int[] iv : intervals) {
    int curStart = iv[0];
    int curEnd   = iv[1];
    if (curStart >= lastKeptEnd) {
        lastKeptEnd = curEnd;  // no overlap — keep, advance end
    }
    else {
        removed++;             // overlap — remove current (ends later)
    }
}

Pattern 4: Merge + Gap Walk

Copy// Clip → sort by start → merge → walk gaps between merged intervals
// Step 1: clip bookings to window
List<int[]> inWindow = new ArrayList<>();
for (int[] booking : booked) {
    int clippedStart = Math.max(booking[0], winStart);
    int clippedEnd   = Math.min(booking[1], winEnd);
    if (clippedStart < clippedEnd) {
        inWindow.add(new int[]{clippedStart, clippedEnd});
    }
}
inWindow.sort((a, b) -> a[0] - b[0]);

// Step 2: merge overlapping bookings (same as Pattern 1)
List<int[]> merged = new ArrayList<>();
int[] cur = inWindow.get(0).clone();
for (int i = 1; i < inWindow.size(); i++) {
    int[] next = inWindow.get(i);
    if (next[0] <= cur[1]) {
        cur[1] = Math.max(cur[1], next[1]);
    } else {
        merged.add(cur);
        cur = next.clone();
    }
}
merged.add(cur);

// Step 3: walk gaps — every space between merged bookings is free
int cursor = winStart;
for (int[] booking : merged) {
    if (booking[0] > cursor) {
        result.add(new int[]{cursor, booking[0]});  // gap before this booking
    }
    cursor = Math.max(cursor, booking[1]);
}
if (cursor < winEnd) {
    result.add(new int[]{cursor, winEnd});           // trailing gap
}

General Templates

Overlap Check Reference

CopyNo overlap (a ends before b starts):  a[1] < b[0]
Overlap (touching counts):             a[1] >= b[0]   (i.e., NOT a[1] < b[0])

Problem 1: Merge Intervals [B75-56]

Merge all overlapping intervals and return the non-overlapping result.

Example:

CopyInput:  [[1,3],[2,6],[8,10],[15,18]]  →  [[1,6],[8,10],[15,18]]
Input:  [[1,4],[4,5]]                 →  [[1,5]]

Key Insight:

• Sort by start time. For each interval: if it starts after the last merged interval ends, there is no overlap — add it. Otherwise, extend the last interval's end to the maximum of both ends. Touching intervals ([1,4],[4,5]) do overlap — use < not <= in the non-overlap check.
• Problem 4 (Find Available Windows) contains this exact pattern as its Step 2. If you practice Problem 4, you have already solved this.

Solution:

Copypublic int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> result = new ArrayList<>();
    for (int[] iv : intervals) {
        if (result.isEmpty() || result.get(result.size()-1)[1] < iv[0]) {
            result.add(iv);
        }
        else {
            result.get(result.size()-1)[1] = Math.max(result.get(result.size()-1)[1], iv[1]);
        }
    }
    return result.toArray(new int[0][]);
}

Complexity:

Problem 2: Insert Interval ⭐ MUST DO [B75-57]

Given a sorted list of non-overlapping intervals, insert a new interval and merge if necessary.

Example:

CopyInput:  intervals = [[1,3],[6,9]],  newInterval = [2,5]   →  [[1,5],[6,9]]
Input:  intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]],  newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

Key Insight:

• Three phases: (1) add all intervals that end before the new one starts — no overlap, (2) merge all intervals that overlap with the new one by expanding its boundaries, (3) add all remaining intervals. No sorting needed since input is already sorted.

Solution:

Copypublic int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0, n = intervals.length;

    while (i < n && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i]); // phase 1: before new
        i++;
    }

    while (i < n && intervals[i][0] <= newInterval[1]) {   // phase 2: overlapping
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval);

    while (i < n) {
        result.add(intervals[i]); // phase 3: after new
        i++;
    }
    return result.toArray(new int[0][]);
}

Complexity:

Problem 3: Non-overlapping Intervals ⭐ MUST DO [B75-435]

Return the minimum number of intervals to remove so the rest are non-overlapping.

Example:

CopyInput:  [[1,2],[2,3],[3,4],[1,3]]  →  1   (remove [1,3])
Input:  [[1,2],[1,2],[1,2]]        →  2

Key Insight:

• Sort by end time. Greedy: always keep the interval that ends earliest — it leaves the most room for future intervals. When two intervals overlap, remove the one with the later end time (which is always the current one, since we sorted by end). Track the end of the last kept interval.

Solution:

Copypublic int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);     // sort by end time
    int removed = 0, end = Integer.MIN_VALUE;
    for (int[] iv : intervals) {
        if (iv[0] >= end) {
            end = iv[1];    // no overlap — keep this interval
        }
        else {
            removed++;      // overlap — remove current (it ends later)
        }
    }
    return removed;
}

Complexity:

Problem 4: Find Available Windows ⭐ MUST DO

Given a list of booked intervals and a search window [winStart, winEnd), return all free time gaps within the window.

Example:

CopyInput:  booked = [[1,3],[5,8],[6,10]], winStart = 0, winEnd = 12
        clip → [[1,3],[5,8],[6,10]]  (all within window)
        sort → [[1,3],[5,8],[6,10]]
        merge → [[1,3],[5,10]]
        gaps:  [0,1], [3,5], [10,12]
Output: [[0,1],[3,5],[10,12]]

Input:  booked = [[2,6]], winStart = 0, winEnd = 10
Output: [[0,2],[6,10]]

Key Insight:

• Three-step pipeline that extends Merge Intervals (Problem 1): (1) clip all bookings to the search window — anything outside is irrelevant, (2) sort by start and merge overlaps exactly like Problem 1, (3) invert the merged list by walking gaps — every space between consecutive merged bookings is free time, plus any leading or trailing space. Practicing this problem covers the full Sort+Merge template plus the gap-walk pattern, making Problem 1 redundant as a standalone must-do.

Solution:

Copypublic List<int[]> findAvailableWindows(int[][] booked, int winStart, int winEnd) {
    List<int[]> result = new ArrayList<>();

    if (booked == null || booked.length == 0) {
        result.add(new int[]{winStart, winEnd});
        return result;
    }

    // Step 1: clip bookings to window
    List<int[]> inWindow = new ArrayList<>();
    for (int[] booking : booked) {
        int clippedStart = Math.max(booking[0], winStart);
        int clippedEnd   = Math.min(booking[1], winEnd);
        if (clippedStart < clippedEnd) {
            inWindow.add(new int[]{clippedStart, clippedEnd});
        }
    }
    if (inWindow.isEmpty()) {
        result.add(new int[]{winStart, winEnd});
        return result;
    }
    inWindow.sort((a, b) -> a[0] - b[0]);

    // Step 2: merge overlapping bookings
    List<int[]> merged = new ArrayList<>();
    int[] cur = inWindow.get(0).clone();
    for (int i = 1; i < inWindow.size(); i++) {
        int[] next = inWindow.get(i);
        if (next[0] <= cur[1]) {
            cur[1] = Math.max(cur[1], next[1]);  // extend current
        } else {
            merged.add(cur);
            cur = next.clone();
        }
    }
    merged.add(cur);

    // Step 3: walk gaps between merged bookings
    int cursor = winStart;
    for (int[] booking : merged) {
        if (booking[0] > cursor) {
            result.add(new int[]{cursor, booking[0]});  // gap before this booking
        }
        cursor = Math.max(cursor, booking[1]);
    }
    if (cursor < winEnd) {
        result.add(new int[]{cursor, winEnd});           // trailing gap
    }
    return result;
}

Complexity:

Quick Reference Table

When to Use Each Pattern

Sort by Start + Merge

• Input is unsorted intervals; need to collapse all overlaps into a flat non-overlapping list
• Check last.end < current.start for no overlap (strict < — touching intervals do overlap)
• Extend last.end = max(last.end, current.end) whenever overlap is detected

Three-Phase Scan (Insert into Sorted)

• Input is already sorted and non-overlapping; inserting exactly one new interval
• Phase 1 boundary: intervals[i][1] < newInterval[0] — interval ends before new one starts
• Phase 2 boundary: intervals[i][0] <= newInterval[1] — interval starts before new one ends
• O(n) — no sorting needed because input is pre-sorted

Sort by End + Greedy Keep

• Minimization problem: remove the fewest intervals to eliminate all overlaps
• Sort by end gives the greedy choice property (earliest-deadline-first)
• Only update end = iv[1] when you KEEP an interval, not when you remove it

Merge + Gap Walk

• Problem gives booked/occupied intervals; asks for free/available time within a window
• Clip first — any booking outside the window is irrelevant and causes off-by-one bugs if kept
• After merging, walk gaps: track cursor = winStart, advance it to booking[1] after each merged interval; any space before booking[0] is a free gap

Common Mistakes to Avoid

Overlap Condition Mistakes

1. Wrong no-overlap check in merge — use strict < (last.end < current.start); using <= incorrectly treats touching intervals like [1,4],[4,5] as non-overlapping when they should be merged
2. Insert interval: wrong phase 2 condition — use intervals[i][0] <= newInterval[1] (not strict <); strict < would miss touching intervals that need merging

Greedy Sort Key Mistakes

3. Non-overlapping: sorting by start instead of end — sorting by start does not give the greedy choice property; you must sort by end time for the earliest-deadline-first strategy to work correctly
4. Non-overlapping: updating end on removal — only update end = iv[1] in the keep branch (if), never in the removal branch (else); updating on removal uses a later end and breaks the tracking

Gap Walk Mistakes

5. Skipping the clip step — bookings that extend outside the window must be clipped before sorting and merging; keeping them causes gaps to be missed or boundaries to be wrong
6. Forgetting the trailing gap — after walking all merged bookings, check if (cursor < winEnd) and add the final gap; it is easy to emit every internal gap and miss the one after the last booking
7. Updating cursor on gap instead of booking end — always advance cursor = Math.max(cursor, booking[1]) after processing a booking, not when emitting a gap; the max guards against bookings fully contained within a previous one