Interval Scheduling and Merging Intervals

Interval problems show up constantly in scheduling, calendar apps, and resource-allocation systems: you’re given a list of time ranges and need to either combine the ones that overlap or pick the largest possible set that doesn’t conflict. Both tasks are solved with the same core trick — sort the intervals first, then sweep through them once, making a greedy decision at each step. This lesson covers two closely related patterns: merging overlapping intervals into their union, and interval scheduling, where you select the maximum number of non-overlapping intervals (the classic "activity selection" problem). Both are staples of coding interviews and both are genuinely useful in real systems like calendar merging and CPU job scheduling.

Overview / How it works

An interval is just a pair [start, end] representing a range — a meeting from 1pm to 3pm, a highway closure from mile 12 to mile 18, a sensor reading valid from timestamp 100 to 400. Interval problems ask one of two questions: "which of these ranges overlap, and what do they merge into?" or "how many of these ranges can I keep if no two are allowed to overlap?" Both questions are solved by the same two-step recipe: sort first, then sweep once. Sorting turns an unordered pile of ranges into a sequence where any interval that could possibly overlap the current one is guaranteed to be its immediate neighbor in the sorted order — so a single left-to-right pass, comparing each interval only to the most recent decision, is enough. Without sorting you would need to compare every pair of intervals, which is O(n²).

This lesson treats intervals as closed and inclusive on both ends, and — this detail matters and trips people up — treats touching intervals as overlapping. That is, [1, 3] and [3, 6] are considered overlapping because they share the point 3, so they merge into [1, 6]. If your problem defines "overlap" differently (e.g., half-open ranges where [1, 3) and [3, 6) do not touch), you only need to flip a single comparison operator between <= and < — but decide which convention you’re using before you write the comparison, because the two give different answers.

Merging overlapping intervals

To merge, sort by start time. Walk through the sorted list keeping a "current merged interval" (initialized to the first interval). For each subsequent interval, if its start is less than or equal to the current merged interval’s end, they overlap — extend the current interval’s end to the larger of the two ends. Otherwise the current interval is finished; push it to the results and start a new current interval. Because the input was sorted by start, once you’ve moved past an interval it can never come back and overlap something earlier — that’s what makes a single forward pass correct.

Interval scheduling maximization (activity selection)

Here the goal is different: pick the largest possible subset of intervals such that none of the chosen ones overlap (this models, for example, scheduling the maximum number of non-conflicting meetings in one room). The greedy rule is to sort by end time — not start time, and not duration; a common mistake is assuming the shortest intervals should be picked first, but that can strand you with a bad choice later. The proof idea (an "exchange argument") is: whichever valid schedule you compare against, you can always swap its first-finishing interval for the earliest-ending interval overall without making the schedule worse, because finishing earlier only leaves more room, never less. Applying that swap repeatedly shows the greedy earliest-end-time choice is always at least as good as any other schedule.

Time and Space Complexity

Algorithm	Time	Space	Why
Merge intervals	O(n log n)	O(n)	Sorting dominates at O(n log n); the merge sweep afterward is a single O(n) pass. Space is O(n) for the output list.
Interval scheduling maximization	O(n log n)	O(n)	Same shape: O(n log n) to sort by end time, then one O(n) greedy pass.
Insert interval (already sorted, non-overlapping)	O(n)	O(n)	No sort needed — the input invariant means one linear pass finds where the new interval fits and which ones it swallows.
Naive pairwise overlap check	O(n²)	O(1)	Comparing every interval against every other without sorting — exactly what the sort-then-sweep pattern avoids.

In every row, n is the number of intervals. The sort is almost always the bottleneck; the sweep itself is linear because each interval is visited a constant number of times — it either extends the current range, starts a new one, or is skipped.

Examples

Example 1: Merging overlapping meeting times

The most direct application: given a pile of meeting ranges, collapse the overlapping ones into their union.

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []
    intervals.sort(key=lambda pair: pair[0])
    merged: list[list[int]] = [intervals[0]]
    for start, end in intervals[1:]:
        last_start, last_end = merged[-1]
        if start <= last_end:
            merged[-1][1] = max(last_end, end)
        else:
            merged.append([start, end])
    return merged


meetings = [[1, 3], [2, 6], [8, 10], [15, 18], [9, 12]]
print(merge_intervals(meetings))

Output:

[[1, 6], [8, 12], [15, 18]]

After sorting by start time, meetings becomes [[1, 3], [2, 6], [8, 10], [9, 12], [15, 18]]. The sweep starts with [1, 3] as the current interval. [2, 6] starts at 2, which is <= 3, so it overlaps — the current interval becomes [1, 6]. [8, 10] starts at 8, greater than 6, so it does not overlap; [1, 6] is finalized and [8, 10] becomes the new current interval. [9, 12] starts at 9, which is <= 10, so it merges into [8, 12]. Finally [15, 18] starts at 15, greater than 12, so [8, 12] is finalized and [15, 18] stands alone. Three merged ranges come out.

Example 2: Selecting the maximum number of non-overlapping activities

Now the opposite goal: given a batch of candidate activities, keep as many non-conflicting ones as possible instead of merging them.

def max_non_overlapping(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    sorted_intervals = sorted(intervals, key=lambda pair: pair[1])
    selected: list[tuple[int, int]] = []
    last_end = float("-inf")
    for start, end in sorted_intervals:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected


activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
result = max_non_overlapping(activities)
print(result)
print(len(result))

Output:

[(1, 4), (5, 7), (8, 11), (12, 16)]
4

Sorting by end time happens to leave this particular list in its original order, since it was already listed with non-decreasing end times. The sweep tracks last_end, starting at negative infinity. (1, 4) is picked (last_end becomes 4). (3, 5) and (0, 6) both start before 4, so they’re skipped. (5, 7) starts at 5, which is >= 4, so it’s picked (last_end becomes 7). (3, 9), (5, 9), and (6, 10) all start before 7 and are skipped. (8, 11) starts at 8, >= 7, so it’s picked (last_end becomes 11). (8, 12) and (2, 14) start before 11 and are skipped. (12, 16) starts at 12, >= 11, so it’s picked. Four non-overlapping activities survive — the maximum possible for this input.

Example 3: Inserting a new interval into a sorted list

A related interview-favorite: you already have a sorted, non-overlapping list of intervals and need to insert one more, merging it with whatever it touches.

def insert_interval(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    start, end = new_interval
    index = 0
    n = len(intervals)

    while index < n and intervals[index][1] < start:
        result.append(intervals[index])
        index += 1

    while index < n and intervals[index][0] <= end:
        start = min(start, intervals[index][0])
        end = max(end, intervals[index][1])
        index += 1

    result.append([start, end])

    while index < n:
        result.append(intervals[index])
        index += 1

    return result


existing = [[1, 3], [6, 9]]
updated = insert_interval(existing, [2, 5])
print(updated)

Output:

[[1, 5], [6, 9]]

existing is already sorted and non-overlapping: [[1, 3], [6, 9]], and the new interval is [2, 5]. The first loop looks for intervals that end strictly before the new interval starts (2); [1, 3] ends at 3, which is not less than 2, so that loop never runs and index stays 0. The second loop absorbs every interval overlapping the new one: [1, 3] starts at 1, which is <= 5 (the new interval’s end), so it overlaps — start becomes min(2, 1) = 1 and end becomes max(5, 3) = 5, and index advances to 1. Now intervals[1] is [6, 9], whose start (6) is not <= 5, so the loop stops. The merged interval [1, 5] is appended. The final loop copies the one remaining untouched interval, [6, 9], onto the result.

How it works step by step

Let’s trace merge_intervals one operation at a time on [[1, 3], [2, 6], [8, 10], [15, 18], [9, 12]] so you can see exactly what the algorithm does at each point, the way the interpreter would execute it.

1. Sort by start: the list becomes [[1, 3], [2, 6], [8, 10], [9, 12], [15, 18]].
2. Initialize: merged = [[1, 3]] — the first interval seeds the result.
3. Compare [2, 6]: start 2 <= current end 3, so overlap. Update the last entry’s end to max(3, 6) = 6. merged = [[1, 6]].
4. Compare [8, 10]: start 8 <= current end 6? No. No overlap — append it as a new current interval. merged = [[1, 6], [8, 10]].
5. Compare [9, 12]: start 9 <= current end 10, so overlap. Update the last entry’s end to max(10, 12) = 12. merged = [[1, 6], [8, 12]].
6. Compare [15, 18]: start 15 <= current end 12? No. Append. merged = [[1, 6], [8, 12], [15, 18]].
7. Done: every interval has been visited exactly once; return the three merged ranges.

Notice the algorithm only ever looks at merged[-1] — the most recently finalized-or-growing interval — never anything earlier. That’s the payoff of sorting: it guarantees nothing later in the list could possibly overlap an interval two or more positions back.

Common Mistakes

Mistake 1: forgetting to sort before merging

The merge algorithm’s correctness depends entirely on the input being sorted by start time first. Skipping that step and sweeping through intervals in whatever order they arrived produces wrong merges whenever a later, larger interval should have absorbed an earlier one.

def merge_wrong(intervals: list[list[int]]) -> list[list[int]]:
    merged: list[list[int]] = [intervals[0]]
    for start, end in intervals[1:]:
        last_start, last_end = merged[-1]
        if start <= last_end:
            merged[-1][1] = max(last_end, end)
        else:
            merged.append([start, end])
    return merged

# Bug: intervals were never sorted first, so overlaps
# that aren't already adjacent in the input order get missed.

Called on [[8, 10], [1, 3], [2, 6]], this starts with merged = [[8, 10]] and then compares [1, 3] against it — start 1 is nowhere near end 10, so it’s wrongly treated as non-overlapping and appended separately, even though a properly sorted pass would have merged [1, 3] and [2, 6] together first. The fix is one line: call intervals.sort(key=lambda pair: pair[0]) before the loop, exactly as in the working merge_intervals shown earlier.

Mistake 2: an off-by-one on the overlap boundary

Using a strict < where the problem’s convention calls for <= (or vice versa) silently changes which intervals count as overlapping.

def merge_off_by_one(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda pair: pair[0])
    merged: list[list[int]] = [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

# Bug: using strict "<" instead of "<=" treats touching
# intervals like [1, 3] and [3, 6] as non-overlapping, so
# they never get merged even though they share the point 3.

Called on [[1, 3], [3, 6]], the comparison 3 < 3 is false, so the two intervals are kept apart as [[1, 3], [3, 6]] instead of merging into [1, 6]. Whether that’s actually a bug depends on your problem’s definition of overlap — the fix is to be deliberate: use <= if touching intervals should merge (the convention this lesson uses), or keep < and document that touching intervals are intentionally treated as separate.

Best Practices

• Always sort before sweeping, and sort by the field the algorithm actually needs: start time for merging overlaps, end time for maximizing the count of non-overlapping intervals.
• Decide up front whether touching intervals count as overlapping, and be consistent about <= versus < in every comparison — mixing conventions inside one function is a frequent source of bugs.
• list.sort() mutates in place; if the caller still needs the original order, sort a copy with sorted(intervals, key=...) instead.
• If intervals already come pre-sorted and non-overlapping (as in the insert-interval pattern), don’t re-sort the whole list on every insertion — that turns an O(n) operation into O(n log n) for no reason.
• For a large, static set of intervals you’ll query repeatedly against many different ranges, the sort-and-sweep pattern shown here is the wrong tool — look into an interval tree or a sorted structure with binary search instead.
• Initialize a "last selected end" tracker with float("-inf") (or any sentinel lower than any real value) so the very first interval is never skipped by the comparison logic.

Practice Exercises

1. Meeting rooms: Given the intervals [[0, 30], [5, 10], [15, 20]], write a function that returns the minimum number of meeting rooms required to host all of them without conflicts. Hint: track starts and ends separately, sort each independently, and sweep through time counting how many meetings are simultaneously in progress. Expected answer for this input: 2.
2. Interval intersection: Given two lists of sorted, non-overlapping intervals representing two people’s busy times, e.g. [[1, 3], [5, 9]] and [[2, 4], [6, 8]], find all the time ranges where both are busy at once. Hint: a two-pointer walk through both lists at the same time, one pointer per list. Expected answer: [[2, 3], [6, 8]].
3. Minimum removals: Given [[1, 2], [2, 3], [3, 4], [1, 3]], find the minimum number of intervals to remove so that the rest don’t overlap. Hint: this is the activity-selection maximum count in disguise — first find the largest non-overlapping subset, then subtract its size from the total. Expected answer: 1.

Summary

• Interval problems are solved by sorting once, then sweeping once — sorting turns a potential O(n²) all-pairs comparison into an O(n log n) sort plus an O(n) linear pass.
• To merge overlapping intervals, sort by start time; extend the current merged interval whenever the next interval’s start is <= the current end, otherwise start a new merged interval.
• To maximize the count of non-overlapping intervals (activity selection), sort by end time and greedily keep any interval whose start is >= the last kept interval’s end — this greedy choice is provably optimal via an exchange argument.
• Both patterns run in O(n log n) time, O(n) space, dominated by the sort; a pass over already-sorted, non-overlapping intervals (like inserting a new one) only needs O(n) time.
• Decide your overlap convention (does touching count?) up front and apply <= vs < consistently — this is the single most common source of off-by-one bugs in interval code.
• Sort a copy with sorted() instead of list.sort() if the caller’s original order must be preserved.