LeetCode Interval Problems: Merge, Insert, and Schedule

Interval problems appear constantly in coding interviews. They look diverse but almost all share the same first step: sort by start time. Once sorted, a single scan can merge, insert, count overlaps, or schedule rooms. This guide covers the core patterns.

The Golden Rule

Almost every interval problem starts with:

intervals.sort(key=lambda x: x[0])

Sorting by start time guarantees that as you scan left to right, you only need to compare each interval against the previous one (or a running state). Without sorting, you would need O(n^2) pairwise comparisons.

Pattern 1: Merge Overlapping Intervals (LeetCode #56)

Given a list of intervals, merge all overlapping ones.

Key insight: After sorting, two consecutive intervals overlap if and only if the second starts before or at the first’s end.

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        last_end = merged[-1][1]

        if start <= last_end:
            # overlapping — extend the current interval
            merged[-1][1] = max(last_end, end)
        else:
            # no overlap — start a new interval
            merged.append([start, end])

    return merged

print(merge([[1,3],[2,6],[8,10],[15,18]]))
# [[1, 6], [8, 10], [15, 18]]

print(merge([[1,4],[4,5]]))
# [[1, 5]]

Complexity: O(n log n) time for sorting, O(n) space for the result.

Walkthrough

Input (sorted): [1,3] [2,6] [8,10] [15,18]

Step 1: merged = [[1,3]]
Step 2: [2,6] — 2 <= 3, overlap! Extend to [1,6]
Step 3: [8,10] — 8 > 6, no overlap. Add [8,10]
Step 4: [15,18] — 15 > 10, no overlap. Add [15,18]

Result: [[1,6], [8,10], [15,18]]

Pattern 2: Insert Interval (LeetCode #57)

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

Key insight: Split the problem into three phases: intervals entirely before, intervals that overlap, and intervals entirely after.

def insert(intervals: list[list[int]],
           new: list[int]) -> list[list[int]]:
    result = []
    i = 0
    n = len(intervals)

    # phase 1: add all intervals that end before new starts
    while i < n and intervals[i][1] < new[0]:
        result.append(intervals[i])
        i += 1

    # phase 2: merge all overlapping intervals with new
    while i < n and intervals[i][0] <= new[1]:
        new[0] = min(new[0], intervals[i][0])
        new[1] = max(new[1], intervals[i][1])
        i += 1
    result.append(new)

    # phase 3: add remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

print(insert([[1,3],[6,9]], [2,5]))
# [[1, 5], [6, 9]]

print(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))
# [[1, 2], [3, 10], [12, 16]]

Complexity: O(n) time (input is already sorted), O(n) space.

Pattern 3: Meeting Rooms (Can Attend All?)

Given a list of meeting intervals, determine if a person can attend all of them. This is simply checking for any overlap.

def can_attend_all(intervals: list[list[int]]) -> bool:
    intervals.sort(key=lambda x: x[0])

    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False  # overlap found

    return True

print(can_attend_all([[0,30],[5,10],[15,20]]))  # False
print(can_attend_all([[7,10],[2,4]]))            # True

Pattern 4: Minimum Meeting Rooms (Sweep Line)

Find the minimum number of conference rooms required. This is the classic sweep-line problem.

Key insight: Convert each interval into two events: a start (+1 room) and an end (-1 room). Sort events and sweep through them, tracking the running count.

import heapq

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0

    # approach 1: min-heap of end times
    intervals.sort(key=lambda x: x[0])
    heap = [intervals[0][1]]  # end time of first meeting

    for start, end in intervals[1:]:
        if start >= heap[0]:
            heapq.heappop(heap)  # reuse the room
        heapq.heappush(heap, end)

    return len(heap)

print(min_meeting_rooms([[0,30],[5,10],[15,20]]))  # 2
print(min_meeting_rooms([[7,10],[2,4]]))            # 1

Alternative: Event-Based Sweep

def min_rooms_sweep(intervals: list[list[int]]) -> int:
    events = []
    for start, end in intervals:
        events.append((start, 1))   # meeting starts
        events.append((end, -1))    # meeting ends

    events.sort()
    max_rooms = current = 0

    for _, delta in events:
        current += delta
        max_rooms = max(max_rooms, current)

    return max_rooms

print(min_rooms_sweep([[0,30],[5,10],[15,20]]))  # 2

Complexity: O(n log n) time, O(n) space.

Pattern 5: Non-Overlapping Intervals (LeetCode #435)

Find the minimum number of intervals to remove so no two intervals overlap. This is the classic interval scheduling maximization problem.

Key insight: Sort by end time. Greedily keep the interval that ends earliest, giving the most room for future intervals.

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])  # sort by END
    removals = 0
    prev_end = float('-inf')

    for start, end in intervals:
        if start >= prev_end:
            prev_end = end  # keep this interval
        else:
            removals += 1   # remove this interval

    return removals

print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # 1
print(erase_overlap_intervals([[1,2],[1,2],[1,2]]))         # 2

Decision Guide

Situation	Pattern	Sort By
Merge overlapping intervals	Scan and extend	Start time
Insert into sorted list	Three-phase scan	Already sorted
Check for any overlap	Pairwise neighbor check	Start time
Count max simultaneous	Sweep line / heap	Start time or events
Maximize non-overlapping	Greedy keep earliest end	End time

Overlap Detection Cheat Sheet

Two intervals [a1, a2] and [b1, b2] overlap if and only if:

a1 < b2 and b1 < a2

They do NOT overlap if one ends before the other starts:

a2 <= b1 or b2 <= a1

This simple check is the foundation of every interval problem. Memorize it.

Common Pitfalls

Sorting by the wrong key: Merge problems sort by start. Scheduling maximization sorts by end. Mixing these up gives wrong answers.

Inclusive vs exclusive boundaries: Pay attention to whether endpoints are inclusive. [1,5] and [5,10] may or may not overlap depending on the problem definition. Read the problem statement carefully.

Forgetting edge cases: Empty input, single interval, and fully nested intervals (like [1,10] containing [2,3]) are common edge cases that break naive implementations.

Interval problems are some of the most predictable in coding interviews. Sort, scan, and apply the right overlap logic. Once you internalize these five patterns, most interval questions become straightforward.