# Interval Algorithm Interview Patterns (2025)

Source: https://www.techinterview.org/post/3233463966/interval-algorithm-interview-patterns/
Updated: 2026-07-05 · techinterview.org

## 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] <= start:
            heapq.heappop(heap)   # earliest room frees before this start, reuse it
        heapq.heappush(heap, end)
    return len(heap)


def min_meeting_rooms_two_pointer(intervals: list[list[int]]) -> 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](https://techinterview.org/meta-interview-guide/)

🏢 Asked at: [Apple Interview Guide 2026: iOS Systems, Hardware-Software Integration, and iCloud Architecture](https://techinterview.org/apple-interview-guide/)

🏢 Asked at: [Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture](https://techinterview.org/databricks-interview-guide/)

🏢 Asked at: [Atlassian Interview Guide](https://techinterview.org/atlassian-interview-guide/)

🏢 Asked at: [Coinbase Interview Guide](https://techinterview.org/coinbase-interview-guide/)