Core Interval Pattern
Interval problems involve ranges [start, end] and typically ask: merge overlapping intervals, find gaps, count the minimum resources needed, or determine if a new interval fits. The universal first step: sort intervals by start time. After sorting, adjacent intervals in the sorted order are the only candidates for merging (a later interval can never overlap an earlier non-adjacent interval after sorting). This reduces O(n^2) comparison to O(n) linear scan after the O(n log n) sort.
Merge Overlapping Intervals (LC 56)
Sort by start. Iterate: if the current interval overlaps the last merged interval (current.start <= last.end), merge by extending the end: last.end = max(last.end, current.end). Otherwise, the current interval is disjoint — add it as a new merged interval.
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 mergedLC 57 (Insert Interval): insert a new interval into a sorted, non-overlapping list. Three phases: add all intervals that end before new interval starts (no overlap). Merge all intervals that overlap the new interval (new.start <= interval.end and interval.start <= new.end). Add the remaining intervals. O(n) time since the list is already sorted.
Meeting Rooms (LC 252, 253)
LC 252 (Can attend all meetings?): sort by start, check if any adjacent pair overlaps (intervals[i].start < intervals[i-1].end). O(n log n). LC 253 (Minimum conference rooms): sort start times and end times separately. Use two pointers: one for starts (i), one for ends (j). If start[i] < end[j]: a new meeting starts before any current one ends — need one more room, i++. Else: a meeting ended before this one starts — reuse its room, i++ and j++. Track the maximum rooms in use at any point.
def min_meeting_rooms(intervals):
starts = sorted(x[0] for x in intervals)
ends = sorted(x[1] for x in intervals)
rooms = 0
max_rooms = 0
j = 0
for i in range(len(starts)):
if starts[i] < ends[j]:
rooms += 1
max_rooms = max(max_rooms, rooms)
else:
rooms -= 1
j += 1
return max_roomsNon-Overlapping Intervals (LC 435)
Find the minimum number of intervals to remove to make the rest non-overlapping. Greedy: sort by end time (earliest deadline first). Greedily keep intervals with the earliest end time that do not overlap the previously kept interval. The number of removed intervals = total – kept. This is equivalent to the classic Activity Selection problem: select the maximum number of non-conflicting activities to maximize the kept count.
Employee Free Time (LC 759)
Given N employees each with M work intervals: find all intervals when no employee is working (the free time). Merge all intervals from all employees into one sorted list (flatten and sort by start). Then find gaps between consecutive merged intervals. Gaps are the free time intervals. O(N*M log(N*M)) for the sort. This is merge intervals applied to a multi-source dataset.
Interval DP Pattern
Some interval problems require DP over sub-intervals rather than greedy. The general form: dp[i][j] = optimal answer for the range [i, j]. Fill the DP table by increasing interval length. For each interval length L and each starting index i: for each split point k between i and j: dp[i][j] = combine(dp[i][k], dp[k+1][j]). Examples: Burst Balloons (LC 312), Strange Printer (LC 664), Minimum Cost to Cut Stick (LC 1547). These have O(n^3) time and O(n^2) space. The split-point enumeration (all k between i and j) is the key loop.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide