Interval Scheduling / Merging

Imagine you are building a calendar application. A user submits their meetings for the day: 9:00 to 10:30, 10:00 to 11:00, 12:00 to 13:00, 14:00 to 16:00, 15:30 to 17:00. You need to display a simplified view showing occupied time blocks, so overlapping meetings should be collapsed into a single block. You also need to answer a different question: given a set of optional events, what is the maximum number the user can attend without conflicts? These are the two core interval problems, merging and scheduling, and despite looking similar, they require fundamentally different approaches.

Merge intervals

LeetCode 56 presents the merging problem: given a list of intervals, combine all overlapping ones and return the set of non-overlapping intervals that cover the same ranges.

The algorithm

The key observation is that if you sort intervals by their start time, then overlapping intervals must be adjacent in the sorted order. Two intervals [a, b] and [c, d] overlap if and only if c <= b (assuming a <= c after sorting). This means you can solve the problem in a single left-to-right pass.

1. Sort the intervals by start time.
2. Initialize your result with the first interval.
3. For each subsequent interval, compare its start with the end of the last interval in your result.
4. If they overlap (current start <= last end), extend the last interval's end to the maximum of the two ends.
5. If they don't overlap, append the current interval as a new entry.

Worked example

Take the intervals [[1,3], [2,6], [8,10], [15,18]]. After sorting by start (they already are), we begin:

• Start with result = [[1,3]].
• Next interval [2,6]: start 2 <= end 3 of last result, so they overlap. Extend: result = [[1,6]].
• Next interval [8,10]: start 8 > end 6, no overlap. Append: result = [[1,6], [8,10]].
• Next interval [15,18]: start 15 > end 10, no overlap. Append: result = [[1,6], [8,10], [15,18]].

That is the final answer. Three merged intervals covering the original four.

What if the input were [[1,4], [0,4]]? After sorting by start we get [[0,4], [1,4]]. The second interval starts at 1, which is <= 4, so we merge. The result is [[0,4]]. Notice that the merge extends to the max of the two ends, which is still 4 here.

Code

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

The sort is $O(n \log n)$ and the merge pass is $O(n)$, so the overall time complexity is $O(n \log n)$. Space is $O(n)$ for the output list (or $O(1)$ extra if you merge in place, depending on how you count the result).

Maximum non-overlapping intervals (the scheduling problem)

For LeetCode 435, you are given a set of intervals and must find the minimum number of intervals to remove so that the rest are non-overlapping. Equivalently, you can frame this as: what is the maximum number you can select so that none of them overlap?

This is the classic activity selection or interval scheduling problem, and it has a beautiful greedy solution, but the sort key changes.

Why sorting by end time is critical

For merging, we sorted by start time. For scheduling, we must sort by end time. This is not interchangeable. Here is why.

Suppose you have intervals [1,10], [2,3], [4,5]. If you sort by start time and greedily pick the first interval [1,10], you have locked yourself into a choice that blocks both of the other intervals. You get 1. But the optimal answer is 2: pick [2,3] and [4,5].

Sorting by end time gives [2,3], [4,5], [1,10]. Now the greedy picks [2,3] first (ends earliest), then [4,5] (starts at 4 >= 3), then skips [1,10] (starts at 1 < 5). We get 2, which is optimal.

The greedy proof

The greedy choice property is straightforward: among all intervals that don't conflict with your current selection, picking the one that ends earliest leaves the maximum amount of remaining time for future intervals. No other choice can do better, because any interval that ends later than the earliest-ending one would leave strictly less room (or at best the same room) for what comes after. You can formalize this with an exchange argument. If an optimal solution picks some interval X instead of the earliest-ending compatible interval Y, you can swap X for Y without breaking feasibility and without reducing the count, because Y ends no later than X.

Worked example

Intervals: [[1,2], [2,3], [3,4], [1,3]]. Sort by end: [[1,2], [2,3], [1,3], [3,4]].

• Pick [1,2]. Set boundary = 2.
• [2,3]: start 2 >= boundary 2. Pick it. Boundary = 3.
• [1,3]: start 1 < boundary 3. Skip.
• [3,4]: start 3 >= boundary 3. Pick it. Boundary = 4.

Maximum non-overlapping count = 3. If the problem asks for minimum removals, the answer is 4 - 3 = 1.

Code

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

This counts the maximum compatible set, then subtracts from the total to get minimum removals. Time is $O(n \log n)$ for the sort; the scan is $O(n)$. Space is $O(1)$ beyond the sort.

Meeting Rooms II: minimum rooms needed

LeetCode 253 asks a different question: given a list of meeting time intervals, find the minimum number of conference rooms required so that no two overlapping meetings share a room.

This is not the same as "how many overlap at the peak?", though that is exactly what it computes. The approach is different from both merging and scheduling.

The heap approach

Sort the meetings by start time. Maintain a min-heap of end times, where each entry represents a room currently in use and when its current meeting finishes.

For each meeting:

1. If the earliest-ending room (top of the heap) finishes at or before this meeting's start, that room is free, so pop it.
2. Push this meeting's end time onto the heap (either reusing the freed room or allocating a new one).

The size of the heap at its maximum is the answer.

import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    heap = []
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    return len(heap)

Walk through [[0,30], [5,10], [15,20]]:

• [0,30]: heap is empty, push 30. Heap = [30]. Rooms = 1.
• [5,10]: earliest end is 30, but 30 > 5, so we can't reuse. Push 10. Heap = [10, 30]. Rooms = 2.
• [15,20]: earliest end is 10, and 10 <= 15, so pop 10 and push 20. Heap = [20, 30]. Rooms = 2.

Answer: 2 rooms.

Time is $O(n \log n)$ for the sort and $O(n \log n)$ total for the heap operations. Space is $O(n)$ for the heap.

Alternative: the sweep line

An equivalent approach treats each interval as two events: a start (+1) and an end (-1). Sort all events by time (breaking ties by processing ends before starts if intervals like [1,2] and [2,3] should not conflict), then sweep through, maintaining a running count. The peak count is the answer. This is conceptually cleaner but the heap approach is more commonly asked in interviews.

Insert interval

With LeetCode 57, you are given a sorted, non-overlapping list of intervals and a new interval to insert, and must return the merged result. The strategy is:

1. Add all intervals that end before the new interval starts (no overlap, they go straight to the result).
2. Merge all intervals that overlap with the new interval (extend the new interval's start and end as needed).
3. Add all intervals that start after the new interval ends.

def insert(intervals, newInterval):
    result = []
    i = 0
    # Intervals entirely before newInterval
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
    # Overlapping intervals, merge into newInterval
    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)
    # Intervals entirely after
    while i < len(intervals):
        result.append(intervals[i])
        i += 1
    return result

This runs in $O(n)$ time since the input is already sorted: no sorting step is needed.

Why the sort key matters so much

It is worth emphasizing one more time: the sort key is not a minor implementation detail. It determines whether the greedy argument holds.

• Merge intervals: sort by start. You need adjacent overlapping intervals to be next to each other. Sorting by end would interleave intervals whose starts are far apart, breaking the merge logic.
• Non-overlapping selection: sort by end. The greedy argument depends on "ending earliest leaves the most room." Sorting by start does not guarantee this property and produces suboptimal results.
• Meeting Rooms II: sort by start (so you process meetings in chronological order), but use a heap keyed on end times to track room availability.

Getting the sort key wrong is the single most common mistake on interval problems.

Complexity summary

All of these problems share a common spine, sorting the intervals and then making a single pass with a simple invariant, but the details of what you sort by and what you track during the pass differ in ways that matter. Mastering the distinctions is what turns interval problems from tricky into routine.

Recognizing this pattern

You're probably looking at interval scheduling / merging when:

• The input is a list of pairs $[start, end]$ representing intervals: meetings, bookings, ranges on a number line, or time windows.
• The question is one of: "merge overlapping intervals," "max non-overlapping intervals," "minimum rooms / resources," "can you attend all meetings," or "insert an interval and re-merge."
• The answer depends on overlap relationships, not on the absolute values inside each interval.
• The first algorithmic instinct should be sort, then sweep once, and the only real decision is whether to sort by start or by end.
• Constraints are large enough ($n$ up to $10^5$) that $O(n^2)$ pairwise checks won't pass, but $O(n \log n)$ sorting is fine.

Common templates:

• Merge overlapping intervals: sort by start, merge into result when ranges touch. Example: Merge Intervals.
• Max non-overlapping (or min removals): sort by end, greedily take the interval with earliest end among non-conflicting ones. Example: Non-overlapping Intervals.
• Minimum rooms / concurrent count: sort by start, use a min-heap on end times (or sweep events). Example: Meeting Rooms II.
• Insert and merge: single linear pass through sorted intervals, splitting into "before / overlapping / after." Example: Insert Interval.
• Can attend all meetings (overlap check): sort by start, scan for any overlap with predecessor. Example: Meeting Rooms.