Merge Intervals Problems: 13 That Actually Appear in Interviews

You solve one interval problem. Feel smart. Then you see Meeting Rooms. Then Non-overlapping Intervals. Then Employee Free Time. Somewhere around problem five, you realize you haven't been solving different problems. You've been solving the same four problems in different Halloween costumes.

These 13 merge intervals problems, ordered by concept complexity, teach each idea once and then drill it through variants. Work through them in order. By problem 13, the Skyline Problem won't look like a hard problem. It will look like Meeting Rooms II that put on a blazer and asked to speak to a manager.

Before Any Merge Intervals Problem, Get These Three Right

Before the problems, the toolkit. Skip this section and you will fail problems you "understand" because you'll get these details backwards.

The overlap test: intervals [a, b] and [c, d] overlap when a <= d and c <= b. The complement is cleaner: they do NOT overlap when b < c or d < a. Memorize the complement. Your brain reaches for the wrong one under pressure.

The sort key: sort by start time for merging; sort by end time for greedy removal. Getting this backwards is the most common wrong solution on LC 435. It looks right. It passes some test cases. It is wrong.

The merge step: always max(current_end, new_end), never just new_end. If interval B is fully contained inside A, using new_end silently truncates A. This one bug fails [[1,10],[2,5]] with no error message, which is the worst kind of bug.

The full template with event sweep tie-breaking is in Merge Intervals: The Template Behind Every Scheduling Problem. This post is the companion problem set.

Tier 1: Get These Wrong and Everything Else Fails

1. Merge Intervals (LC 56, Medium)

What it teaches: The foundational sort-and-scan loop.

Sort by start. Walk through. If the current interval's start is <= the last merged end, extend. Otherwise push a new 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)  # containment bug lives here
        else:
            merged.append([start, end])
    return merged

The max() call is not optional. On [[1,10],[2,5]], end is 5 but the running end is already 10. Replacing it gives you [1,5] and a wrong answer that passes most test cases. This is the bug that kills confident people who "already know merge intervals."

2. Meeting Rooms (LC 252, Easy)

Can one person attend every meeting? Sort by start. Check consecutive pairs. If intervals[i][1] > intervals[i+1][0], two meetings collide. Return False.

def canAttendMeetings(intervals):
    intervals.sort()
    for i in range(len(intervals) - 1):
        if intervals[i][1] > intervals[i+1][0]:
            return False
    return True

One pass, no extra memory. The value of this problem is pattern recognition: sorted adjacency check equals overlap detection. You'll use this implicit check inside every harder problem.

3. Remove Covered Intervals (LC 1288, Medium)

What it teaches: A secondary sort key that isn't obvious until it breaks without it.

Sort by start ascending, end descending. Track the running max end. Any interval whose end falls within the current max end is covered.

def removeCoveredIntervals(intervals):
    intervals.sort(key=lambda x: (x[0], -x[1]))
    count, max_end = 0, 0
    for _, end in intervals:
        if end > max_end:
            count += 1
            max_end = end
    return count

The descending end sort is load-bearing. Two intervals sharing the same start (say [2,8] and [2,5]) need the longer one processed first. Without the -x[1] tiebreak, [2,5] looks non-covered before [2,8] is seen, and you overcount. It's a two-character fix that most people discover after submitting a wrong answer.

Tier 2: Sort by End, Not Start

This is where most people go wrong on their first pass. The problem says "intervals" and your hand reaches for start-time sort. Stop. Activity selection problems sort by end.

4. Non-overlapping Intervals (LC 435, Medium)

What it teaches: Activity selection. Sort by end, not start.

Keep as many intervals as possible by greedily picking each interval that starts at or after the last kept interval ends. Removals = total minus kept.

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])  # sort by END
    kept, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end:
            kept += 1
            last_end = end
    return len(intervals) - kept

Sorting by start here is provably wrong. The exchange argument runs: if any optimal solution skips the interval with the earliest end, you can swap it in without making anything worse. See The Greedy Algorithm: When Local Optimal Means Global Optimal for the formal proof.

5. Minimum Number of Arrows to Burst Balloons (LC 452, Medium)

Same greedy as LC 435. One character difference in the overlap condition. The character matters.

Sort by end. Fire an arrow at the rightmost point of the current balloon. Every balloon starting before or at that position is also burst. Advance when a balloon's start exceeds the last arrow position.

def findMinArrowShots(points):
    points.sort(key=lambda x: x[1])
    arrows, last_shot = 1, points[0][1]
    for start, end in points[1:]:
        if start > last_shot:   # strict greater-than
            arrows += 1
            last_shot = end
    return arrows

The one difference from LC 435: the overlap condition is strict (> not >=). Balloons touching at a single point are still burst by the same arrow. Getting this wrong passes 80% of test cases and fails on edge inputs. Submitting and getting a wrong answer on this specific detail is a rite of passage.

Tier 3: Pre-Sorted Input Needs a Different Loop

6. Insert Interval (LC 57, Medium)

What it teaches: Handling pre-sorted, non-overlapping input without re-sorting.

The input is guaranteed sorted and non-overlapping. Walk in three phases: copy all intervals ending before the new one starts, merge everything that overlaps, append the rest.

def insert(intervals, newInterval):
    result, i = [], 0
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        result.append(intervals[i]); i += 1
    while i < len(intervals) 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)
    result.extend(intervals[i:])
    return result

The two while-loop boundary conditions are exact mirrors of the non-overlap predicate. First loop: end before new start. Second loop: start before or at new end. Getting either boundary off by one shifts an interval into the wrong phase, silently producing the wrong output.

Tier 4: The Heap Is Load-Bearing

7. Meeting Rooms II (LC 253, Medium)

Track the maximum number of simultaneously overlapping intervals. This is the core algorithm behind calendar conflict detection, CPU scheduling, and about a dozen LeetCode problems you haven't realized are the same thing yet.

Use a min-heap of end times. For each meeting sorted by start, pop any meeting that finished before this one starts, then push the new one. The heap size is the room count.

import heapq

def minMeetingRooms(intervals):
    intervals.sort()
    heap = []
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)
    return len(heap)

The heap only needs end times, not full intervals. That compression is worth saying aloud during the interview. It signals you understand what information actually drives the decision. For a full breakdown, see The Heap Data Structure: A Complete Binary Tree Hiding in an Array.

8. Divide Intervals Into Minimum Number of Groups (LC 2406, Medium)

Meeting Rooms II in disguise. Specifically, it's wearing a hat and a fake mustache.

Same algorithm, different story: assign each interval to a group with no internal overlaps, minimize groups. The minimum equals the maximum concurrent overlap at any point.

The event sweep makes this cleaner. Emit +1 at each start and -1 at each end + 1 (the +1 handles closed intervals so touching endpoints land in different groups correctly).

def minGroups(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end + 1, -1))
    events.sort()
    current = max_groups = 0
    for _, delta in events:
        current += delta
        max_groups = max(max_groups, current)
    return max_groups

The end + 1 offset is not cosmetic. Without it, two intervals touching at the same point (like [1,5] and [5,9]) incorrectly count as overlapping, adding a phantom group. This is one of those bugs that you debug for twenty minutes before realizing the fix is adding 1 to a single number.

Tier 5: Two Sorted Lists, Two Pointers

9. Interval List Intersections (LC 986, Medium)

What it teaches: Two-pointer technique across two sorted lists.

Walk one pointer per list. Compute the intersection of the current pair. Advance the pointer whose interval ends first.

def intervalIntersection(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])
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
    return result

Advancing whichever pointer ends first is the key claim to justify aloud. The interval ending later might still intersect the next interval in the other list, so you cannot advance it yet. This is the part of the solution that separates "got it by luck" from "can explain it."

10. Meeting Scheduler (LC 1229, Medium)

LC 986 with a duration filter and an early exit. The problem sounds more complicated because it involves two people's calendars. It isn't.

Find the earliest slot in both people's availability lists long enough for a required meeting. Sort both, apply the two-pointer intersection, return the first result that meets the duration requirement.

def minAvailableDuration(slots1, slots2, duration):
    slots1.sort(); slots2.sort()
    i = j = 0
    while i < len(slots1) and j < len(slots2):
        lo = max(slots1[i][0], slots2[j][0])
        hi = min(slots1[i][1], slots2[j][1])
        if hi - lo >= duration:
            return [lo, lo + duration]
        if slots1[i][1] < slots2[j][1]:
            i += 1
        else:
            j += 1
    return []

When you see "earliest common time slot," reach for LC 986 with an early-exit condition. The pattern is identical.

Tier 6: The Heap Gets Complicated

11. Employee Free Time (LC 759, Hard)

What it teaches: Flatten nested input, merge it, then find the gaps.

Most attempts try to track free time incrementally per employee. They get lost. The actual solution is embarrassingly simple once you see it.

Collect all intervals from all employees. Sort by start. Run LC 56's merge. The spaces between merged intervals are the answer.

def employeeFreeTime(schedule):
    intervals = sorted(
        [iv for emp in schedule for iv in emp],
        key=lambda x: x.start
    )
    merged_end = intervals[0].end
    result = []
    for iv in intervals[1:]:
        if iv.start > merged_end:
            result.append(Interval(merged_end, iv.start))
            merged_end = iv.end
        else:
            merged_end = max(merged_end, iv.end)
    return result

The hard part is noticing you need LC 56 first and a gap scan second. Once you flatten everything into a single sorted list, the problem is a ten-line solution. The difficulty rating is a lie.

12. Meeting Rooms III (LC 2402, Hard)

What it teaches: Two-heap simulation for priority-based resource assignment.

Rooms are assigned by lowest number when available. If none are free, delay the meeting until the earliest-ending active meeting finishes, preserving the original duration. This requires two heaps: one for available rooms, one for active meetings.

import heapq

def mostBooked(n, meetings):
    meetings.sort()
    available = list(range(n))  # min-heap of free room numbers
    active = []                 # min-heap of (end_time, room_number)
    count = [0] * n
    for start, end in meetings:
        while active and active[0][0] <= start:
            _, room = heapq.heappop(active)
            heapq.heappush(available, room)
        if available:
            room = heapq.heappop(available)
            heapq.heappush(active, (end, room))
        else:
            earliest_end, room = heapq.heappop(active)
            heapq.heappush(active, (earliest_end + (end - start), room))
        count[room] += 1
    return count.index(max(count))

The delayed end time is earliest_end + (end - start), not earliest_end + end. The meeting keeps its original duration. It just starts late. This distinction is easy to miss when you're staring at the code at 1 AM, which is exactly when most people solve this problem.

13. The Skyline Problem (LC 218, Hard)

What it teaches: Max-heap event sweep where intervals represent heights, not time slots.

This problem has a reputation. The reputation is somewhat deserved and somewhat theater. It IS Meeting Rooms II, except the "rooms" are height levels and the priority is maximum height rather than earliest end. If you've solved problems 7 through 12, the structure is familiar.

Treat each building's left and right edges as events. At a left edge, push the building's height onto a max-heap tagged with its right edge. Before reading the current max height, lazily pop any building whose right edge has passed.

import heapq

def getSkyline(buildings):
    # Start events: (x, -height, right_edge). End events: (x, 0, 0).
    # Negative height ensures starts sort before ends at the same x,
    # and taller starts sort first among starts at the same x.
    events = sorted(
        [(l, -h, r) for l, r, h in buildings] +
        [(r, 0, 0) for _, r, _ in buildings]
    )
    heap = [(0, float('inf'))]  # sentinel: zero height, never expires
    result = []
    for x, neg_h, end in events:
        if neg_h < 0:
            heapq.heappush(heap, (neg_h, end))
        while heap[0][1] <= x:    # lazy removal of expired buildings
            heapq.heappop(heap)
        cur_max = -heap[0][0]
        if not result or result[-1][1] != cur_max:
            result.append([x, cur_max])
    return result

The event sort order is not arbitrary. Start events use negative heights so that at the same x-coordinate, starts sort before ends, and taller starts sort before shorter starts. Getting the sort wrong produces phantom skyline segments that appear in none of the example test cases and all of the edge cases.

If you want to see how these patterns feel under real interview pressure, SpaceComplexity runs voice-based mock interviews with rubric-based feedback across problem-solving, communication, and optimization. Working through these 13 problems is preparation. Narrating the overlap predicate while an interviewer watches is the actual test.