What you'll learn

  1. Quick answer
  2. Recognizing an Interval Scheduling Problem
  3. Merge Intervals: Sort by Start, Sweep and Combine
  4. Minimum Meeting Rooms: Sort Starts and Ends Separately
  5. Maximum Non-Overlapping Meetings: Sort by End, Not Start
  6. The Real Decision: Sort by Start or by End?
  7. Why the Sort Is the Whole Trick (and What Breaks Without It)
  8. FAQ

Quick Answer

Interval scheduling problems — merge overlapping intervals, find the minimum meeting rooms needed, or pick the maximum number of non-overlapping meetings — all reduce to one move: sort the intervals first, then sweep through once. The variant decides whether you sort by start time or end time, and that single choice is the entire trick: we verified with real code that sorting by the wrong field silently produces a wrong answer on the maximum-non-overlapping variant.

Recognizing an Interval Scheduling Problem

The pattern: the input is a list of (start, end) pairs — meeting bookings, time ranges, event windows — and the question asks something about how they relate to each other: merge the ones that overlap, find the peak number active at once, or pick the largest subset that don't overlap at all. That's a genuinely different shape of problem from two pointers or sliding window, which reason about one contiguous sequence, or prefix sums, which answer range-aggregate queries over one array. Here, the raw material is a set of ranges, and the question is about relationships between them.

The fix in almost every case is the same first move: sort first. Overlap can only be reasoned about cheaply once neighboring intervals sit in a fixed, predictable order — on unsorted input, checking whether any two intervals overlap is an O(n²) pairwise comparison. There are three canonical variants worth knowing cold: merge intervals (collapse overlapping ranges into their union), minimum meeting rooms (find the peak number of intervals active at the same instant), and maximum non-overlapping intervals, also called activity selection (pick the largest subset with no overlaps at all).

Merge Intervals: Sort by Start, Sweep and Combine

Sort by start time. Walk through once, keeping a running “merged” list. If the next interval's start is less than or equal to the last merged interval's end, they overlap (or touch) — extend the last merged interval's end to whichever is larger. Otherwise, the current interval starts a fresh group. Here's the actual tested implementation:

def merge_intervals(intervals):
    if not intervals:
        return []
    intervals = sorted(intervals, key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last_start, last_end = merged[-1]
        if start <= last_end:               # overlap (touching counts)
            merged[-1] = [last_start, max(last_end, end)]
        else:
            merged.append([start, end])
    return merged

Run against three inputs, including one where the sort actually matters. Real, unedited output:

input:  [[1, 3], [2, 6], [8, 10], [15, 18]]
output: [[1, 6], [8, 10], [15, 18]]

input:  [[1, 4], [4, 5]]
output: [[1, 5]]

input:  [[1, 4], [0, 4]]   (unsorted on purpose)
output: [[0, 4]]

The third case is the one worth staring at: the input arrives as [[1, 4], [0, 4]], out of start order. Without the sort inside the function, the sweep would compare [1, 4] against [0, 4] directly and never realize they overlap in the way the algorithm expects, because the sweep logic assumes the current interval's start can only move forward. The sort isn't a style choice here — it's a correctness requirement the algorithm depends on. The second case, [[1, 4], [4, 5]] merging into [1, 5], confirms the <= in the overlap check: touching endpoints count as overlapping in this formulation, not just strictly overlapping ranges. Complexity is O(n log n), dominated entirely by the sort — the sweep itself is a single O(n) pass.

Minimum Meeting Rooms: Sort Starts and Ends Separately

This variant asks a different question — not what to merge, but how many rooms are needed at the busiest single moment. The approach: split the intervals into two separate sorted arrays, one of all start times and one of all end times, then walk both with two pointers. Each time the next start happens before the earliest currently-running meeting ends, a new room is needed; each time a meeting ends before the next one starts, a room frees up for reuse. This is really finding the maximum number of intervals overlapping at any single point in time, using a two-pointer sweep over event times as an alternative to a full sweep-line with +1/-1 events (both approaches work; this is the one that was implemented and verified here):

def min_meeting_rooms(intervals):
    if not intervals:
        return 0
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)
    rooms = max_rooms = 0
    s = e = 0
    n = len(intervals)
    while s < n:
        if starts[s] < ends[e]:
            rooms += 1
            s += 1
            max_rooms = max(max_rooms, rooms)
        else:
            rooms -= 1
            e += 1
    return max_rooms

Real, verified output on three inputs:

input: [[0, 30], [5, 10], [15, 20]]
rooms needed: 2

input: [[7, 10], [2, 4]]
rooms needed: 1

input: [[9, 10], [4, 9], [4, 17]]
rooms needed: 2

The third case is the instructive one: two meetings, [4, 9] and [4, 17], both start at the same instant, so two rooms are needed right at time 4 — even though the first of those two ends quickly at 9, well before the third meeting [9, 10] even starts. The algorithm correctly reports 2, not 3, because it's tracking the peak simultaneous count, and that peak of 2 only ever happens once, at time 4. Complexity is again O(n log n) for the two sorts, with an O(n) sweep on top.

Maximum Non-Overlapping Meetings: Sort by End, Not Start

This is the classic activity selection problem, and it's the one variant where the sort key genuinely flips the correctness of the answer. The greedy rule: sort by end time, then repeatedly pick the next interval whose start is at or after the last chosen interval's end. The intuition for why this is provably optimal: picking whichever compatible interval frees up the timeline soonest can never leave you worse off than any other valid choice at that step — it's a textbook exchange-argument proof, and it specifically requires sorting by end time to work.

def max_non_overlapping_meetings(intervals):
    if not intervals:
        return 0, []
    intervals = sorted(intervals, key=lambda x: x[1])   # sort by END, not start
    count = 1
    chosen = [intervals[0]]
    last_end = intervals[0][1]
    for start, end in intervals[1:]:
        if start >= last_end:
            count += 1
            chosen.append([start, end])
            last_end = end
    return count, chosen

Run on the standard 11-interval example used to teach this problem:

input: [[1,4],[3,5],[0,6],[5,7],[3,8],[5,9],[6,10],[8,11],[8,12],[2,13],[12,14]]
max count: 4
chosen: [[1, 4], [5, 7], [8, 11], [12, 14]]

Now the proof that the sort field actually matters, not just in theory: sorting that exact same 11-interval input by start time instead and running the identical greedy selection produces only 3 non-overlapping meetings — [[0, 6], [6, 10], [12, 14]] — a strictly worse answer than the 4 that sorting by end produces. A smaller, cleaner counterexample makes the failure obvious: for [[1, 10], [2, 3], [4, 5]], sorting by start greedily locks in [1, 10] first (it starts earliest) and gets stuck at a count of 1, while sorting by end correctly picks [2, 3] then [4, 5] for a count of 2. Same greedy shape, different sort key, genuinely different — and wrong — answer. Complexity is O(n log n) for the sort, O(n) for the single greedy pass.

The Real Decision: Sort by Start or by End?

The rule that actually holds across all three variants: if the question is about combining or counting overlap as things unfold chronologically — merge intervals, or the minimum-rooms count — sort by start (meeting rooms additionally needs a separately sorted array of ends, but the primary sweep still walks forward through start order). If the question is a selection problem asking for the largest possible set of non-overlapping intervals, sort by end — the exchange-argument proof behind activity selection specifically depends on end time being the ordering criterion, and the previous section showed with real output exactly how it breaks otherwise.

A quick way to keep the two straight under interview pressure: start-sorting answers “what does the timeline look like as events happen,” which is what merging and room-counting need. End-sorting answers “which option should I lock in first to leave the most room for everything after it,” which is what a greedy selection needs. If a problem asks you to select or count a maximum independent set of intervals and you find yourself reaching for a start-sort out of habit from the other two variants, that's the exact moment to stop and reconsider.

Why the Sort Is the Whole Trick (and What Breaks Without It)

All three algorithms are the same shape underneath: an O(n log n) sort that makes a subsequent O(n) linear sweep valid. The sort isn't an optimization on top of the real algorithm — it is the part that makes the sweep correct at all, exactly as the unsorted [[1, 4], [0, 4]] case demonstrated for merge intervals earlier, and exactly as the start-vs-end comparison just demonstrated for activity selection.

Two follow-ups worth having ready. If the interviewer says the intervals arrive already sorted, the whole solution drops to O(n) — say so, it shows you know exactly where the cost was coming from. If instead they ask for a running answer over a live stream of intervals (rooms being booked and released continuously, not a fixed batch), the two-pointer approach above needs a fixed array up front and doesn't fit — the standard fix is a min-heap keyed on end time, popping off meetings that have already ended before pushing a new one, which supports the same peak-overlap query incrementally. That's a known, standard extension worth naming even if you don't have time left to implement it end to end.

Frequently Asked Questions

How do I know whether to sort by start or end time? If the problem is about merging overlaps or counting how many intervals are active at once, sort by start. If it's a selection problem asking for the maximum number of non-overlapping intervals, sort by end — sorting by start on that variant can silently produce a smaller, wrong answer.
What's the time complexity of these interval algorithms? All three are O(n log n) overall, dominated entirely by the initial sort. The sweep or greedy pass that follows the sort is O(n) on its own.
Do touching intervals count as overlapping, like [1,4] and [4,5]? In the standard formulation used here, yes — a start less than or equal to the previous end counts as an overlap, so [1,4] and [4,5] merge into [1,5]. Some problem statements define this strictly instead, so always confirm the boundary condition with the interviewer before coding.
Is minimum meeting rooms the same as counting maximum overlap? Yes — the minimum number of rooms needed to schedule all the meetings is exactly the maximum number of meetings ever active at the same instant, which is what the two-pointer sweep over sorted starts and ends is computing.
Can I solve minimum meeting rooms with a heap instead of two sorted arrays? Yes — push meeting end times onto a min-heap as you sweep through intervals sorted by start; whenever the heap's smallest end time is less than or equal to the new interval's start, pop it (that room freed up) before pushing the new end time. It's a common alternative, especially for streaming input.
Why does sorting by start time fail for the maximum non-overlapping meetings problem? Sorting by start can lock in an interval that starts earliest but runs very long, blocking out several shorter meetings that would have fit instead. On the classic 11-interval teaching example, start-sorting greedily finds only 3 non-overlapping meetings, while end-sorting correctly finds 4.