What is the key insight for solving the Merge Intervals problem?

Sort intervals by start time first. Then iterate: for each interval, check if it overlaps with the last merged interval. Two intervals [a,b] and [c,d] overlap if c

How do you find the minimum number of meeting rooms required?

Use a min-heap of end times. Sort meetings by start time. For each meeting: if the heap is non-empty and the earliest-ending meeting (heap minimum) ends at or before the current meeting starts, that room is free — replace the heap minimum with the current meeting's end time (reuse the room). Otherwise, push the current meeting's end time (new room needed). The heap size after processing all meetings equals the minimum rooms required. Why min-heap? It gives O(1) access to the room that frees up earliest — exactly what you need to decide whether any room is available. Time: O(n log n). Alternative: sort starts and ends separately, use two pointers. For each start time: if a meeting has ended (end pointer), increment end pointer (room freed); else add a room. Maximum rooms_in_use across all starts = answer.

Why do you sort by end time for the Non-Overlapping Intervals problem?

This is the classic Activity Selection problem — find the maximum number of non-overlapping intervals (equivalently, minimum intervals to remove). Greedy algorithm: sort by end time, then greedily pick each interval that doesn't overlap with the last picked. Sorting by end time is correct because intervals that end earliest leave the most time for future intervals. A counterexample for sorting by start time: intervals [[1,100],[2,3],[4,5],[6,7]]. Sorted by start: pick [1,100] first, which blocks everything else. Sorted by end: pick [2,3], [4,5], [6,7] — 3 intervals kept, only remove [1,100] (1 removal). The greedy proof: if any optimal solution skips an interval we would pick, we can swap it with ours without increasing conflicts (an interval that ends earlier or at the same time can only reduce or maintain future conflicts).

Interval Algorithm Interview Patterns (2025)

⏱ 6 min read

Interval Algorithm Patterns

Interval problems appear constantly in coding interviews — at Google, Meta, Airbnb, and Uber. The key skill: recognizing the overlap condition and knowing when to sort by start vs end time. Most interval problems reduce to one of five patterns.

Overlap Detection

Two intervals [a, b] and [c, d] overlap if and only if: a < d AND c < b (open intervals). For closed intervals [a, b] and [c, d]: a <= d AND c <= b. They do NOT overlap if: b <= c OR d <= a (one ends before the other starts). This single condition is the foundation for all interval algorithms.

Pattern 1: Merge Intervals (LC 56)

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])  # sort by start time
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:       # overlaps with last merged
            merged[-1][1] = max(merged[-1][1], end)  # extend end
        else:
            merged.append([start, end])  # no overlap: add new interval
    return merged

Time O(n log n) for sort, O(n) for merge. The condition start <= merged[-1][1] catches both overlap and touching intervals ([1,3],[3,5] → [1,5]).

Pattern 2: Insert Interval (LC 57)

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

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

    # Merge all overlapping intervals
    while i < n and intervals[i][0] <= new_end:
        new_start = min(new_start, intervals[i][0])
        new_end   = max(new_end,   intervals[i][1])
        i += 1
    result.append([new_start, new_end])

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

Time O(n), no sorting needed since intervals are already sorted. Three passes: before, overlap, after.

Pattern 3: Non-Overlapping Intervals — Minimum Removals (LC 435)

Greedy: sort by end time. Keep an interval if it doesn’t overlap with the previous kept interval. This is the classic “Activity Selection” problem — greedily pick intervals that end earliest to leave room for future intervals.

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[1])  # sort by END time (key insight!)
    kept = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:      # no overlap with last kept interval
            kept += 1
            last_end = end
    return len(intervals) - kept  # removals = total - kept

Why sort by end? Sorting by start doesn’t work — an interval that starts first but ends very late blocks many future intervals. Ending earliest gives the most room for remaining intervals.

Pattern 4: Meeting Rooms II — Minimum Rooms (LC 253)

Find the minimum number of conference rooms required to hold all meetings.

import heapq

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])  # sort by start time
    heap = []   # min-heap of end times (rooms, by when they free up)

    for start, end in intervals:
        if heap and heap[0]  int:
    starts = sorted(s for s, _ in intervals)
    ends   = sorted(e for _, e in intervals)
    rooms = max_rooms = 0
    j = 0
    for start in starts:
        if start < ends[j]:
            rooms += 1
        else:
            j += 1           # a room freed up
        max_rooms = max(max_rooms, rooms)
    return max_rooms

The heap approach is O(n log n). At any point, heap size = current number of rooms in use. The two-pointer approach is cleaner in interviews.

Pattern 5: Employee Free Time (LC 759)

Find all time intervals where ALL employees are free. Merge all schedules, find gaps.

def employee_free_time(schedule: list[list[list[int]]]) -> list[list[int]]:
    # Flatten all intervals
    all_intervals = sorted(
        [interval for employee in schedule for interval in employee],
        key=lambda x: x[0]
    )
    # Merge overlapping intervals
    merged = [all_intervals[0][:]]
    for start, end in all_intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    # Gaps between merged intervals are free time
    free_time = []
    for i in range(1, len(merged)):
        free_time.append([merged[i-1][1], merged[i][0]])
    return free_time

Cheat Sheet

Problem	Sort By	Strategy
Merge intervals	Start time	Extend last merged interval’s end
Insert interval	Already sorted	3 phases: before, merge, after
Min removals	End time	Greedy keep (Activity Selection)
Min meeting rooms	Start time	Min-heap of end times
Free time	Start time	Merge all, find gaps

🏢 Asked at: Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering

🏢 Asked at: Apple Interview Guide 2026: iOS Systems, Hardware-Software Integration, and iCloud Architecture

🏢 Asked at: Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture

🏢 Asked at: Atlassian Interview Guide

🏢 Asked at: Coinbase Interview Guide