Interval Interview Patterns

Interval problems are a cornerstone of technical interviews because they model real-world scheduling, resource allocation, and calendar logic. Mastering them demonstrates your ability to translate a fuzzy, time-based problem into clean, efficient code. While the scenarios vary—from merging meeting times to finding the minimum number of conference rooms—the underlying patterns are remarkably consistent. By understanding two core techniques, sorting and the sweep line algorithm, you can confidently tackle nearly any interval-based question.

The Foundational Approach: Sorting by Start Time

The first and most critical step for nearly all interval problems is to sort the list of intervals by their start time. Why? Processing intervals in chronological order allows you to reason about overlaps and relationships sequentially, turning a two-dimensional overlap-checking problem ($O(n^2)$ if done naively) into a single-pass traversal ($O(n\log n)$ due to sorting).

Imagine you have a list of intervals like $[[1,3],[2,6],[8,10],[15,18]]$. Unsorted, it’s chaotic. Sorted by the first element, the temporal relationships become clear: $[[1,3],[2,6],[8,10],[15,18]]$. You can now iterate through them, holding onto a "current" interval and comparing it to the "next" one. This sorted order is the prerequisite for the three most common pattern variations.

Core Pattern 1: Merging Overlapping Intervals

The merge intervals problem asks you to combine all overlapping intervals into consolidated, non-overlapping ones. After sorting, you initialize a result list with the first interval. Then, for each subsequent interval, you compare it to the last interval in the result list.

The logic is straightforward:

1. If the current interval's start time is less than or equal to the end time of the last merged interval, they overlap. You merge them by updating the end time of the last merged interval to be the maximum of the two ends: last[1] = max(last[1], current[1]).
2. If the current interval starts after the last merged interval ends, there is no overlap. You simply append the current interval to the result list as a new entry.

For our example $[[1,3],[2,6],[8,10],[15,18]]$:

• Start with result = $[[1,3]]$.
• Compare $[2,6]$ to $[1,3]$: 2 <= 3, so they overlap. Merge: $[1,max(3,6)]$ → $[1,6]$. Result is now $[[1,6]]$.
• Compare $[8,10]$ to $[1,6]$: 8 > 6, no overlap. Append: result = $[[1,6],[8,10]]$.
• Compare $[15,18]$ to $[8,10]$: 15 > 10, no overlap. Append: result = $[[1,6],[8,10],[15,18]]$.

This pattern is the workhorse for simplifying complex schedules.

Core Pattern 2: Inserting an Interval into a Sorted List

The insert interval problem gives you a list of non-overlapping intervals sorted by start time and a new interval to insert. The goal is to produce a new sorted list of non-overlapping intervals, merging if necessary. Instead of inserting and then merging, you can solve it in one pass.

Iterate through the existing intervals. All intervals that end before the new interval starts can be added directly to the output—they come entirely before and don't interact. Once you encounter an interval that starts before or at the new interval's end, you enter the "overlap zone." Here, you don't add the existing interval. Instead, you merge the new interval with all overlapping ones by continuously updating the new interval's start (as the minimum of starts) and end (as the maximum of ends). Finally, after the overlap zone, all remaining intervals that start after the merged new interval ends can be added directly.

This approach cleanly handles all cases: insertion at the beginning, middle, or end, and merging with multiple existing intervals.

Core Pattern 3: Finding Minimum Meeting Rooms (Sweep Line Concept)

The meeting rooms II problem asks: "Given a list of meeting times, what is the minimum number of rooms required to hold all meetings without conflict?" This is where the sweep line algorithm shines. Instead of looking at whole intervals, we think about events in time.

Imagine a vertical line sweeping from left to right across the timeline of all meetings. Every time a meeting starts, we need a room. Every time a meeting ends, we free a room. The maximum number of rooms needed concurrently is our answer.

The implementation is elegant:

1. Separate all start times and end times into two sorted lists.
2. Use two pointers to "sweep" through time. Increment a count of active meetings when you see a start event, and decrement it when you see an end event.
3. Track the maximum value of count ever reached.

For intervals $[[0,30],[5,10],[15,20]]$:

• Starts: $[0,5,15]$
• Ends: $[10,20,30]$
• Sweep:
• Time 0 (start): count=1, max=1
• Time 5 (start): count=2, max=2
• Time 10 (end): count=1, max=2
• Time 15 (start): count=2, max=2
• Time 20 (end): count=1, max=2
• Time 30 (end): count=0
• Minimum rooms needed = 2.

This technique efficiently solves for peak concurrent resource usage.

Advanced Application: Sweep Line for Complex Overlaps

The sweep line concept extends beyond counting. It can be used to answer questions like "Given two sets of intervals, find their intersection" or "Find the time when the most people are online." The core idea remains: break intervals into start and end events, sort all events, and process them in order while maintaining a counter or set of active intervals. For intersection problems, you might track the number of active sets. When the count equals the number of sets (e.g., 2 for two people's free/busy schedules), you are within a common interval. This makes the sweep line an indispensable tool for complex overlapping scenarios that simple pairwise merging cannot handle.

Common Pitfalls

1. Forgetting to Sort: This is the most frequent critical error. Attempting to solve interval problems on unsorted data leads to incorrect logic and missed overlaps. Always sort by start time as your first step, unless the problem explicitly states the input is pre-sorted.
2. Incorrect Overlap Condition: The condition for two intervals $[a,b]$ and $[c,d]$ to overlap is not simply $c<b$. The correct condition is $c\le b$ and $a\le d$. However, when intervals are sorted by start time, you only need to check if the new start is less than or equal to the previous end. Misunderstanding this leads to off-by-one errors, especially with questions about "touching" intervals (e.g., $[1,2]$ and $[2,3]$—should they merge?).
3. Updating the Wrong End Time During a Merge: When merging two overlapping intervals $[a,b]$ and $[c,d]$, the new end time is $max(b,d)$, not simply $d$. The second interval might be completely contained within the first (e.g., $[1,10]$ and $[3,4]$). Failing to take the maximum results in an incorrectly shortened interval.
4. Inefficient Insertion: A common mistake in the "insert interval" problem is to append the new interval, sort the entire list, and then run a merge. This works but is less efficient ($O(n\log n)$) than the optimal single-pass solution ($O(n)$). Interviewers look for the optimal approach.

Summary

• Sort First: Virtually every interval problem begins by sorting the list of intervals by their start time. This enables sequential, logical processing.
• Master the Big Three: The merging, inserting, and meeting rooms (sweep line) patterns cover the vast majority of interview questions. Understand the conditional logic and pointer management for each.
• Sweep Line is Your Power Tool: For problems about counting concurrent events or finding common times, model starts and ends as separate events. Processing these in sorted order tracks active counts efficiently.
• Mind the Edge Cases: Pay close attention to whether intervals that just touch (end == start) are considered overlapping, and always use $max()$ when merging end times.
• Think in Terms of Resources: Interval problems often model real constraints like rooms, servers, or employees. Framing the problem this way can help you choose between a simple merge and a sweep line approach.