Merge Intervals

Used for problems involving overlapping ranges (time slots, events, schedules). ~10-15% of array problems fall here.

Identify this pattern when:

• Input is a list of [start, end] pairs
• Problem asks to merge/insert/find overlap/count non-overlapping intervals
• Keywords: "meeting rooms", "schedule", "overlap", "free time"

---

Core Template — Sort + Merge

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

    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        if start <= last_end:                    # overlap
            merged[-1][1] = max(last_end, end)  # extend
        else:
            merged.append([start, end])         # no overlap, add new

    return merged

Two intervals overlap when: start_B <= end_A

---

Insert Interval (no pre-sort needed)

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

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

    # 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)

    # 3. Add remaining
    result.extend(intervals[i:])
    return result

---

Meeting Rooms II — Min Rooms Needed

import heapq

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

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

    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)  # reuse room
        else:
            heapq.heappush(heap, end)     # need new room

    return len(heap)

---

Non-Overlapping Intervals — Min Removals

Greedy: keep intervals with earliest end time. Count how many to remove.

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])  # sort by END (greedy)
    count = 0
    last_end = float('-inf')

    for start, end in intervals:
        if start >= last_end:
            last_end = end  # keep this interval
        else:
            count += 1      # remove this (it overlaps)

    return count

---

Problems & Patterns

---

Time & Space

---

Key Rules

1. Sort by start for merge/insert problems
2. Sort by end for greedy "keep as many as possible" problems
3. Two intervals [a,b] and [c,d] overlap if c <= b (not c < b — adjacent = not overlapping in most problems, check problem statement)
4. When merging: new_end = max(prev_end, curr_end) — handles one inside another

---

Related

• [[DSA/DSA Techniques for Interviews/Sorting Algorithms]] — merge intervals require sort
• [[DSA/DSA Techniques for Interviews/09. Heap & Priority Queue]] — min-heap for meeting rooms
• [[DSA/DSA Techniques for Interviews/02. Two Pointers]] — two-pointer scan variant