Interval Interview Patterns

By /
⏱ 7 min read

Interval problems are a reliable interview topic at every level. The core patterns repeat across dozens of problems – learn the building blocks and you can solve any variant.

Merge Intervals (LC 56)

Sort by start time. Walk through intervals – if the current interval’s start is at or before the previous end, merge by extending the end.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Time: O(n log n) for sort. Space: O(n) for output. The max() call handles the case where the current interval is fully contained within the previous one.

Insert Interval (LC 57)

Linear scan: collect all intervals that end before the new interval starts, merge all overlapping intervals, collect remaining intervals.

def insert(intervals, newInterval):
    result = []
    i = 0
    n = len(intervals)

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

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

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

    return result

Time: O(n). No sorting needed since input is already sorted. The overlap condition is intervals[i][0] <= newInterval[1] – the existing interval starts at or before the new one ends.

Meeting Rooms II (LC 253) – Minimum Conference Rooms

Approach 1: min-heap of end times. Sort meetings by start time, use a heap to track when rooms free up.

import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    # Min-heap: tracks end times of all ongoing meetings
    heap = []
    for start, end in intervals:
        if heap and heap[0] <= start:
            # Reuse the room that freed up earliest
            heapq.heapreplace(heap, end)
        else:
            # Need a new room
            heapq.heappush(heap, end)
    return len(heap)

Approach 2: sweep line (often cleaner to explain in interviews).

def minMeetingRoomsSweep(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))   # meeting starts: +1 room
        events.append((end, -1))    # meeting ends: -1 room
    events.sort()
    max_rooms = rooms = 0
    for time, delta in events:
        rooms += delta
        max_rooms = max(max_rooms, rooms)
    return max_rooms

Note on sweep line sort: when a start and end have the same timestamp, sort by delta so -1 comes before +1. This ensures a room freed at time T can be reused at time T. Adjust: events.sort(key=lambda x: (x[0], x[1])) – since -1 < 1, this naturally handles the tie-breaking.

Non-Overlapping Intervals (LC 435)

Greedy: sort by end time, keep intervals with the earliest end. This maximizes space for future intervals.

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])  # sort by END time
    count = 0
    prev_end = float('-inf')
    for start, end in intervals:
        if start >= prev_end:
            # No overlap - keep this interval
            prev_end = end
        else:
            # Overlap - remove this interval (count removal)
            count += 1
    return count

Minimum Number of Arrows (LC 452)

Same greedy as LC 435. Sort by end, shoot an arrow at each interval’s end that is not yet covered.

def findMinArrowShots(points):
    points.sort(key=lambda x: x[1])
    arrows = 0
    arrow_pos = float('-inf')
    for start, end in points:
        if start > arrow_pos:
            arrows += 1
            arrow_pos = end
    return arrows

LC 435 removes intervals on overlap (strict >=), LC 452 uses strict > because a balloon at [1,2] and [2,3] can both be popped by one arrow at x=2 (endpoints count as intersection).

Employee Free Time (LC 759)

Flatten all intervals from all employees, sort, merge, then find gaps between merged intervals.

def employeeFreeTime(schedule):
    # Flatten all intervals
    all_intervals = []
    for employee in schedule:
        for interval in employee:
            all_intervals.append([interval.start, interval.end])

    all_intervals.sort()

    # Merge overlapping
    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])

    # Find gaps
    free = []
    for i in range(1, len(merged)):
        free.append(Interval(merged[i-1][1], merged[i][0]))

    return free

Sweep Line Algorithm

The sweep line is the general technique behind Meeting Rooms II and many other problems. Convert intervals to events, sort, process in order.

# General sweep line template
def sweep_line(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 'start'))
        events.append((end, 'end'))
    
    # Sort: tie-break so 'end' comes before 'start' at same time
    # This means a room freed at T is available at T
    events.sort(key=lambda x: (x[0], 0 if x[1] == 'end' else 1))
    
    active = 0
    max_active = 0
    for time, event_type in events:
        if event_type == 'start':
            active += 1
            max_active = max(max_active, active)
        else:
            active -= 1
    return max_active

Interval Overlap Check

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

# Overlap (endpoints count):
a1 <= b2 and b1 <= a2

# Overlap (strict - endpoints touching does NOT count):
a1 < b2 and b1 < a2

# No overlap condition (easier to reason about):
a2 < b1 or b2 < a1  # A ends before B starts, or B ends before A starts
# Negate this to get overlap: not (a2 < b1 or b2 = b1 and b2 >= a1

Interview tip: when confused about whether to use strict or non-strict inequality, think about whether [1,2] and [2,3] should be considered overlapping. If yes, use <=. If no (they only share an endpoint), use <.

Pattern Reference: Sort by Start vs Sort by End

Problem typeSort byWhy
Merge intervalsStartProcess in chronological order to detect overlaps
Insert intervalAlready sorted (start)Input constraint
Min rooms neededStart (heap) or both (sweep)Need to match starts with earliest available end
Remove min intervals (no overlap)EndGreedy: keep interval with earliest end to leave room for more
Min arrowsEndSame greedy logic as remove intervals
Find free timeStartMerge first, then find gaps

The rule of thumb: sort by end when you are making greedy keep/remove decisions. Sort by start when you are merging or processing chronologically.

Meta coding interviews test interval merging and sweep line algorithms. See patterns for Meta interview: interval and sweep line problems.

Airbnb system design covers interval-based availability systems. See coding patterns for Airbnb interview: calendar and availability interval problems.

Twitter engineering interviews include interval scheduling problems. See patterns for Twitter/X interview: interval and scheduling problems.

Scroll to Top