Master Interval & Range Interview Problems: Complete Guide

Interval and range problems are a staple in coding interviews, especially at top tech companies. They test your ability to handle overlapping ranges, optimize scheduling, and manage edge cases. From merging calendar events to finding free time slots, these problems have real-world applications in scheduling, resource allocation, and data processing. In this guide, we'll cover the most common interval patterns, provide step-by-step solutions with time and space complexity, and share tips to ace your interview. Whether you're a beginner or looking to brush up, this tutorial will equip you with the tools to tackle any interval problem confidently.

1. Merge Intervals

The classic interval problem: given a collection of intervals, merge all overlapping intervals. The key is to sort by start time, then iterate. If the current interval overlaps with the last merged interval (i.e., current.start <= last.end), update the end to max(last.end, current.end). Otherwise, add the last merged interval to the result and start a new one. Finally, add the last interval after the loop. This runs in O(n log n) due to sorting, and O(n) space for the output.

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

2. Insert Interval

You are given a set of non-overlapping intervals sorted by start time, and a new interval to insert. Merge if necessary. Traverse the list and handle three cases: intervals that end before the new interval starts (add directly), intervals that start after the new interval ends (add new interval then the rest), and overlapping intervals (merge by updating start and end). This is O(n) time and O(n) space.

def insert(intervals, newInterval):
    result = []
    i = 0
    n = len(intervals)
    # add all intervals ending before newInterval starts
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
    # merge 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

3. Meeting Rooms (Leetcode 252)

Determine if a person can attend all meetings. Given an array of meeting time intervals, return true if no two meetings overlap. Simply sort by start time and check if any meeting starts before the previous ends. O(n log n) time, O(1) space.

def canAttendMeetings(intervals):
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][1]:
            return False
    return True

4. Meeting Rooms II (Leetcode 253)

Find the minimum number of conference rooms required. Use a min-heap to track end times of ongoing meetings. Sort intervals by start time. For each meeting, if the room with the earliest end time is free (end <= start), reuse it; otherwise, allocate a new room. The heap size at the end is the answer. O(n log n) time, O(n) space.

import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    heap = []
    heapq.heappush(heap, intervals[0][1])
    for start, end in intervals[1:]:
        if heap[0] <= start:
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    return len(heap)

5. Interval List Intersections (Leetcode 986)

Given two lists of closed intervals, each sorted by start time, return the intersection of these interval lists. Use two pointers. For each pair, the intersection is [max(start1, start2), min(end1, end2)] if start <= end. Then advance the pointer with the smaller end. O(m+n) time, O(k) space for output.

def intervalIntersection(A, B):
    i = j = 0
    result = []
    while i < len(A) and j < len(B):
        start = max(A[i][0], B[j][0])
        end = min(A[i][1], B[j][1])
        if start <= end:
            result.append([start, end])
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
    return result

6. Non-overlapping Intervals (Leetcode 435)

Given a collection of intervals, find the minimum number of intervals to remove to make the rest non-overlapping. Sort by end time (greedy). Keep track of the last end. If current start < last end, it overlaps and we remove it (increment count). Otherwise, update last end. O(n log n) time, O(1) space.

def eraseOverlapIntervals(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end = intervals[0][1]
    for start, end in intervals[1:]:
        if start < last_end:
            count += 1
        else:
            last_end = end
    return count