# Interval Problem Patterns: Merge, Insert, Meeting Rooms & Scheduling

Source: https://www.techinterview.org/post/3233462056/interval-problems-interview-patterns/
Updated: 2026-04-16 · techinterview.org

## Interval Problem Patterns: Merge, Insert, Overlap & Scheduling

Interval problems require manipulating ranges [start, end]. They appear frequently in meeting room, scheduling, and calendar problems. Sort first — almost always the right first move.

## Core Insight: Sort by Start Time

Sorting intervals by start time reduces most problems from O(n²) to O(n log n). After sorting, you only need to compare adjacent intervals.

## Pattern 1: Merge Intervals

Merge all overlapping intervals into the fewest non-overlapping intervals:


```
def merge(intervals):
    intervals.sort()          # sort by start time
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:            # overlap: current start <= prev end
            merged[-1][1] = max(merged[-1][1], end)  # extend end
        else:
            merged.append([start, end])       # no overlap: new interval
    return merged
```


## Pattern 2: Insert Interval

Insert a new interval into a sorted non-overlapping list, merging as needed:


```
def insert(intervals, new_interval):
    result = []
    i = 0
    # Add all intervals ending before new_interval starts
    while i < len(intervals) and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1
    # Merge all overlapping intervals
    while i < len(intervals) and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)
    # Add remaining intervals
    result.extend(intervals[i:])
    return result
```


## Pattern 3: Meeting Rooms (Overlap Detection)


```
# Can attend all meetings? (no overlap)
def can_attend_meetings(intervals):
    intervals.sort()
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][1]:
            return False
    return True

# Minimum rooms needed (max concurrent meetings)
import heapq
def min_meeting_rooms(intervals):
    intervals.sort()
    heap = []  # end times of active meetings
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)
    return len(heap)
```


## Pattern 4: Non-Overlapping Intervals (Minimum Removals)

Greedy: sort by end time, keep as many non-overlapping intervals as possible, count the rest as removals:


```
def erase_overlap_intervals(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[1])  # sort by end time
    removals = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:
            last_end = end   # keep this interval
        else:
            removals += 1    # remove (skip) this interval
    return removals
```


## Pattern 5: Interval List Intersections

Find all intersecting intervals between two sorted lists using two pointers:


```
def interval_intersection(A, B):
    result = []
    i = j = 0
    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
        if lo <= hi:
            result.append([lo, hi])
        # Advance the pointer with earlier end
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
    return result
```


## Pattern 6: Employee Free Time

Find free intervals across all employee schedules. Merge all into one list, then find gaps:


```
def employee_free_time(schedule):
    all_intervals = sorted([iv for emp in schedule for iv in emp], key=lambda x: x[0])
    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 consecutive merged intervals = free time
    return [[merged[i][1], merged[i+1][0]] for i in range(len(merged)-1)]
```


## Classic Interval Problems

| Problem | Algorithm | Complexity |
| --- | --- | --- |
| Merge Intervals | Sort + linear scan | O(n log n) |
| Insert Interval | Three-phase linear scan | O(n) |
| Meeting Rooms I | Sort + compare adjacent | O(n log n) |
| Meeting Rooms II | Sort + min-heap of end times | O(n log n) |
| Non-Overlapping Intervals | Greedy by end time | O(n log n) |
| Interval Intersections | Two pointers | O(m + n) |
| Employee Free Time | Merge all + find gaps | O(n log n) |

## Interview Tips

- Always clarify: are intervals inclusive or exclusive? Can they be empty ([a,a])?

- Sort by start time for merge/insert; sort by end time for greedy non-overlap selection

- The overlap condition: A overlaps B if A.start < B.end AND B.start < A.end (or <= for inclusive)

- For counting concurrent events, the difference array / sweep line technique works in O(n log n)

- [Snap Interview Guide](https://techinterview.org/snap-software-engineer-interview/)

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

- [DoorDash Interview Guide](https://techinterview.org/doordash-software-engineer-interview/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-software-engineer-interview/)

- [Apple Interview Guide](https://techinterview.org/apple-software-engineer-interview/)

- [Meta Interview Guide](https://techinterview.org/meta-software-engineer-interview/)