How do you merge overlapping intervals efficiently?

Sort intervals by start time. Initialize a result list with the first interval. For each subsequent interval, compare its start to the last interval in the result. If start <= result[-1].end, there is overlap—update result[-1].end = max(result[-1].end, current.end). Otherwise, append the current interval. Time O(n log n) for sorting, O(n) for the merge pass. The key: sorting by start ensures you only need to look at the last merged interval.

What is the difference between Meeting Rooms I and Meeting Rooms II?

Meeting Rooms I asks: can one person attend all meetings? Solution: sort by start time, check if any interval's start < previous interval's end. If yes, there's a conflict. Meeting Rooms II asks: what is the minimum number of rooms needed? Solution: sort by start time, use a min-heap of end times for active meetings. If the earliest ending meeting ends before the next one starts, reuse the room; otherwise add a new room. Heap size at the end = minimum rooms needed.

How do you find the minimum number of intervals to remove to make the rest non-overlapping?

This is equivalent to finding the maximum set of non-overlapping intervals and removing the rest. Greedy approach: sort by end time (not start time). Iterate and greedily select each interval that starts at or after the last selected end. Count unselected intervals as removals. Sorting by end time is crucial — it maximizes the intervals we keep, minimizing removals. Time O(n log n).

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

Q: What is the difference between Meeting Rooms I and Meeting Rooms II?

Meeting Rooms I asks: can one person attend all meetings? Solution: sort by start time, check if any interval's start < previous interval's end. If yes, there's a conflict. Meeting Rooms II asks: what is the minimum number of rooms needed? Solution: sort by start time, use a min-heap of end times for active meetings. If the earliest ending meeting ends before the next one starts, reuse the room; otherwise add a new room. Heap size at the end = minimum rooms needed.

Q: How do you find the minimum number of intervals to remove to make the rest non-overlapping?

This is equivalent to finding the maximum set of non-overlapping intervals and removing the rest. Greedy approach: sort by end time (not start time). Iterate and greedily select each interval that starts at or after the last selected end. Count unselected intervals as removals. Sorting by end time is crucial — it maximizes the intervals we keep, minimizing removals. Time O(n log n).

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

Uber Interview Guide

DoorDash Interview Guide

LinkedIn Interview Guide

Apple Interview Guide

Meta Interview Guide