Merge Intervals Interview Patterns: Overlapping Intervals, Meeting Rooms, Calendar Problems (2025)

By /

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 merged

LC 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_rooms

Non-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.

{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “Why do we sort by start time for merge intervals?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “After sorting by start time, any overlapping intervals are adjacent in the sorted order. An interval starting at time S can only overlap intervals that start before S + length of the first interval. Since we process left to right and track the furthest end seen, a gap in the sorted order (current.start > last merged end) guarantees no later interval overlaps the last merged one (they start even later). This reduces an O(n^2) all-pairs overlap check to a single O(n) linear scan after sorting. Without sorting, we would need to compare every pair of intervals to find overlaps. Sorting by start time is the universal first step for any interval merging or scheduling problem.”
}
},
{
“@type”: “Question”,
“name”: “What is the key insight behind the minimum meeting rooms solution?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The minimum number of rooms equals the maximum number of meetings happening simultaneously at any point in time. To find this maximum overlap efficiently: separate and sort start times and end times. Use two pointers: i iterates starts, j iterates ends. At each step, if the next start time is before the next end time, a new meeting begins before any existing one ends (rooms in use increases). Otherwise, a meeting ends before the next begins (rooms in use decreases, reuse the freed room). The maximum rooms value seen during this scan is the answer. This is O(n log n) for sorting and O(n) for the two-pointer scan. The insight: we don’t need to track which meeting is in which room — only the count of simultaneous meetings.”
}
},
{
“@type”: “Question”,
“name”: “How do you determine if two intervals overlap?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Intervals [a, b] and [c, d] overlap if and only if a < d AND c < b (using exclusive ends). Equivalently, they do NOT overlap if b <= c (first ends before second starts) OR d <= a (second ends before first starts). The complement gives the overlap condition: a < d AND c < b. For inclusive ends ([a, b] and [c, d]): they overlap if a <= d AND c merged[i-1].end: free_slots.append(Interval(merged[i-1].end, merged[i].start)). Edge cases: intervals within the same employee can themselves overlap (if the input is not pre-merged). Flatten everything first. Ignore the time before the first meeting and after the last meeting (unbounded free time). O(N*M log(N*M)) time where N = employees, M = intervals per employee.”
}
},
{
“@type”: “Question”,
“name”: “What is the difference between greedy and DP approaches to interval problems?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Greedy works for interval problems where a locally optimal choice is globally optimal. Activity selection (maximize non-overlapping intervals): sort by end time, always pick the earliest-ending interval that does not conflict — this greedy is provably optimal. Minimum interval removals: equivalent to activity selection. Greedy works when the optimal substructure is simple and there are no cross-interval dependencies. DP (interval DP) is needed when the value of a decision depends on the entire sub-interval, not just adjacent intervals. Burst Balloons (LC 312): the value of bursting balloon k depends on its remaining neighbors (the balloons at the boundaries of the sub-interval), which depends on the order of all bursts. Greedy fails here because early choices ripple through in complex ways.”
}
}
]
}

Asked at: Meta Interview Guide

Asked at: Apple Interview Guide

Asked at: LinkedIn Interview Guide

Asked at: Coinbase Interview Guide

Scroll to Top