Interval Interview Patterns

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 type	Sort by	Why
Merge intervals	Start	Process in chronological order to detect overlaps
Insert interval	Already sorted (start)	Input constraint
Min rooms needed	Start (heap) or both (sweep)	Need to match starts with earliest available end
Remove min intervals (no overlap)	End	Greedy: keep interval with earliest end to leave room for more
Min arrows	End	Same greedy logic as remove intervals
Find free time	Start	Merge 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.

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you merge overlapping intervals?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sort intervals by start time. Iterate through: if the current interval overlaps the last merged interval (current.start <= last.end), merge by extending last.end = max(last.end, current.end). Otherwise, push the current interval as a new merged interval. Overlap condition: current.start <= last.end (note: intervals [1,2] and [2,3] overlap at point 2 and should be merged). Time: O(n log n) for sorting, O(n) for the merge pass. LC 56. Edge case: single interval always returns as-is. If intervals can have start == end (point intervals), the same logic applies.”}},{“@type”:”Question”,”name”:”How do you find the minimum number of conference rooms needed?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Two approaches: (1) Min-heap: sort meetings by start time. Use a min-heap storing end times of active meetings. For each meeting, if its start time >= the heap minimum (earliest-ending active meeting), pop the heap (that room is now free). Then push the current meeting end time. The heap size at the end is the answer. O(n log n). (2) Sweep line: create events (+1 for each start, -1 for each end), sort by time (break ties: ends before starts so a meeting ending and starting at the same time uses one room, not two), scan to find the max running sum. Both approaches are O(n log n). The sweep line is simpler to reason about for more complex variants.”}},{“@type”:”Question”,”name”:”What is the greedy strategy for non-overlapping intervals (LC 435)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Greedy: sort intervals by end time. Greedily keep intervals with the earliest end time. For each interval, if it does not overlap the last kept interval (current.start >= last.end), keep it (update last.end). Otherwise, discard it. The number of discarded intervals is the minimum removals needed. Why sort by end? Keeping the interval that ends earliest leaves the most room for future intervals. Sorting by start does not give an optimal greedy. This same greedy solves LC 452 (Minimum Number of Arrows to Burst Balloons) – an arrow can burst all overlapping balloons, and we want minimum arrows = minimum non-overlapping groups.”}},{“@type”:”Question”,”name”:”How does the sweep line algorithm work for intervals?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Create two events for each interval: (start_time, +1) and (end_time, -1). Sort all events by time. For ties (a start and end at the same time), process ends before starts if the interval endpoints are open (they do not share the time point), or starts before ends if they are closed. Scan through events, maintaining a running count. The maximum count is the answer to "maximum overlapping intervals at any point." Applications: maximum concurrent users, minimum conference rooms, maximum bandwidth used at any moment. The sweep line generalizes to 2D (for rectangles) and handles complex event types (start, end, checkpoint queries).”}},{“@type”:”Question”,”name”:”How do you insert a new interval into a sorted non-overlapping list?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Linear scan in O(n): collect all intervals that end before the new interval starts (no overlap, keep as-is). Merge all intervals that overlap the new interval into a single merged interval (overlap = existing.end >= new.start AND existing.start <= new.end). Collect remaining intervals after the merged block. Return: left_unchanged + [merged] + right_unchanged. The merged interval has start = min(new.start, first_overlap.start) and end = max(new.end, last_overlap.end). LC 57. Binary search for the insertion point gives the same O(n) total due to the output construction, but avoids comparing all intervals.”}}]}

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.