Advanced Interval Interview Patterns: Merge, Insert, Meeting Rooms, and Employee Free Time (2025)

Interval Problem Patterns

Interval problems form a distinct category: they involve ranges [start, end] and typically require detecting overlaps, merging, or scheduling. The canonical operations: sort by start time (almost always the first step), sweep line (process events in sorted order), and greedy scheduling (pick intervals that conflict least). Most medium/hard interval problems are variations of these core patterns. Key insight: two intervals [a, b] and [c, d] overlap if and only if a <= d AND c <= b.

Pattern 1: Merge Intervals (LC 56)

Given a list of intervals, merge all overlapping ones. Sort by start time. Iterate: if the current interval overlaps with the last merged interval (curr.start <= last.end), extend the last interval (last.end = max(last.end, curr.end)). Otherwise, add the current interval as a new entry.

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

Pattern 2: Insert Interval (LC 57)

Insert a new interval into a sorted, non-overlapping list. Three phases: (1) Add all intervals that end before new_interval starts. (2) Merge all intervals that overlap with new_interval (update new_interval’s start and end). (3) Add the merged interval and all remaining intervals.

def insert(intervals, new_interval):
    result = []
    i, n = 0, len(intervals)
    # Phase 1: no overlap, before new_interval
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i]); i += 1
    # Phase 2: overlapping intervals
    while i < n 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)
    # Phase 3: remaining
    result.extend(intervals[i:])
    return result

Pattern 3: Meeting Rooms II (LC 253)

Minimum number of conference rooms to schedule all meetings. Two approaches: Sort start and end times separately. Use two pointers. If the next meeting starts before the earliest-ending meeting ends: need a new room. Else: reuse the room (advance end pointer).

def min_meeting_rooms(intervals):
    starts = sorted(i[0] for i in intervals)
    ends   = sorted(i[1] for i in intervals)
    rooms = 0
    max_rooms = 0
    s = e = 0
    while s < len(starts):
        if starts[s] < ends[e]:
            rooms += 1; s += 1
        else:
            rooms -= 1; e += 1
        max_rooms = max(max_rooms, rooms)
    return max_rooms

Alternative: min-heap approach. Sort by start time. Use a min-heap of end times. For each meeting: if heap[0] <= meeting.start, pop (reuse room). Always push meeting.end. Heap size = rooms needed. O(n log n).

Pattern 4: Employee Free Time (LC 759)

Given schedules of k employees (each as a list of non-overlapping intervals), find the common free time for all employees. Key insight: flatten all intervals into one list, sort by start time, merge overlapping intervals to get all “busy” time, then find the gaps between consecutive busy intervals.

def employee_free_time(schedules):
    all_intervals = []
    for schedule in schedules:
        all_intervals.extend(schedule)
    all_intervals.sort(key=lambda x: x.start)

    merged = [all_intervals[0]]
    for iv in all_intervals[1:]:
        if iv.start <= merged[-1].end:
            merged[-1].end = max(merged[-1].end, iv.end)
        else:
            merged.append(iv)

    free_times = []
    for i in range(1, len(merged)):
        free_times.append(Interval(merged[i-1].end, merged[i].start))
    return free_times

Other patterns: Non-Overlapping Intervals (LC 435): minimum removals to make non-overlapping. Greedy: sort by end time, greedily keep the interval that ends earliest. Remove the current interval if it overlaps with the last kept. Interval List Intersections (LC 986): find intersections of two sorted interval lists. Two pointers: advance the pointer of the interval that ends first. The intersection (if any) is [max(a.start, b.start), min(a.end, b.end)].

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the first step in almost every interval problem?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sort the intervals by start time. This makes it possible to process intervals in order and apply greedy decisions (extend the current interval or start a new one). The only exception is problems where end time ordering matters more — for example, "minimum number of intervals to remove" sorts by end time to greedily keep the interval that ends earliest, leaving the most room for remaining intervals.”}},{“@type”:”Question”,”name”:”How do you detect if two intervals overlap?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Intervals [a, b] and [c, d] overlap if and only if a <= d AND c <= b. Equivalently, they do NOT overlap if b < c (first ends before second starts) or d < a (second ends before first starts). For half-open intervals [a, b) and [c, d): they overlap if a < d AND c < b. Always clarify whether endpoints are inclusive or exclusive — it changes the comparison operators.”}},{“@type”:”Question”,”name”:”How does the two-pointer sweep approach solve Meeting Rooms II?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sort start times and end times separately into two arrays. Use pointers s and e starting at 0. If starts[s] < ends[e]: a new meeting begins before the earliest-ending meeting finishes — need an additional room (rooms++, s++). Otherwise: a room becomes free before the next meeting starts — reuse it (rooms–, e++). Track the maximum rooms value. This sweep processes events in sorted order without building an explicit event list.”}},{“@type”:”Question”,”name”:”How do you find all intersections between two sorted interval lists (LC 986)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use two pointers, one for each list. At each step: compute the intersection of the current pair — [max(a.start, b.start), min(a.end, b.end)] — and add it if start <= end. Then advance the pointer of the interval that ends first (it can't intersect with any future interval in the other list). O(m+n) time. The key invariant: the interval that ends first is "used up" and can be discarded.”}},{“@type”:”Question”,”name”:”How do you find the minimum number of non-overlapping intervals to remove (LC 435)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sort by end time. Greedily keep intervals: maintain the end time of the last kept interval. For each interval in sorted order: if it starts at or after the last end time, keep it (update last end time). Otherwise, discard it (it overlaps and ends later than the current kept interval, so discarding it leaves more room). Count discards. This greedy works because keeping the interval with the earliest end time always leaves the most room for future intervals.”}}]}