Intervals: Choose the Sort Key

Interval problems look simple: each one is a start and an end. The difficulty comes almost entirely from knowing how to sort. Sort by the wrong key (start instead of end, or the reverse) and a greedy one-pass solution stops being correct. Pick the right key and most of these become a single scan with one "previous end" variable.

The idea#

After sorting, you walk the intervals once and compare each one only with what you've kept so far. The sort key is what makes that local comparison enough. There are three keys to know, one for each kind of goal:

Sort by start when you need to see intervals arriving in order so you can connect them. If the next start is at or before the current end, they overlap; extend with end = max(end, next_end).
Sort by end when you want to fit in as many as possible. Picking the interval that finishes earliest leaves the most room for everything after it. Any other choice ends later, so it can only block more.
Sort by start ascending, then end descending, (start, -end), for containment. The "big umbrella" comes first among equal starts, so anything it covers appears after it and has an end no larger than the umbrella's.

How to spot it#

In practice, the goal in the problem statement tells you the key. Read the goal, then pick the key from this table.

Goal	Sort key	Why
Merge or combine	Start	You need to see them arriving to connect them
Insert a new interval	Start	Find its slot on the timeline
Max number of non-overlapping items	End	The earliest finish leaves the most room
Min removals to remove overlaps	End	Same as above; keep the earliest finishers
Is it covered? (containment)	`(start, -end)`	Big umbrella first
Max depth or capacity	Events, not intervals	Use a Line Sweep
Intersect two sorted lists	Already sorted	Two pointers; advance the earlier end

Template#

After the sort, the scan has the same shape for every key. Only the key and the overlap test change.

sort intervals by the chosen key
prev_end = minus infinity
for each (start, end) in intervals:
    if start does not overlap prev_end:   # strict or not: read the problem
        start a new group (keep, count, or shoot)
        prev_end = end
    else:
        handle the overlap (extend, skip, or drop)
        prev_end = the end the rule keeps
return the count or the groups

Containment needs a slightly different scan. Sort on (start, -end) and track the largest end seen so far.

sort intervals by (start, -end)       # big umbrella first
max_end = minus infinity
for each (start, end) in intervals:
    if end > max_end:                 # sticks out past every earlier one
        count it as not covered
        max_end = end

Each shape is one $O(n)$ pass after an $O(n \log n)$ sort.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Wrong key. Sorting by start for "max non-overlapping" fails: one long early interval can block many short ones.
Strict vs non-strict comparison. Whether touching endpoints overlap changes > to >=. Check the examples in the problem.
Overwriting the end when merging. Write end = max(end, next_end), not end = next_end. A short interval inside a long one must not shrink it.
Sorting by -end alone for covers. Equal starts must put the longer interval first, so sort on (start, -end).

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first three.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Merge Intervals

Sort by start. If the next start is at or before the last kept end, extend it with max(prev_end, curr_end). Otherwise start a new interval.

Hint: Insert Interval

The input is already sorted, so no sort is needed. Work in three phases: intervals entirely before the new one, intervals that overlap it (merge them into it), and intervals after it.

Hint: Non-overlapping Intervals

Sort by end and keep the earliest finishers. [1, 2] and [2, 3] do not overlap here, so keep an interval when start >= prev_end. The answer is n minus the number kept.

Hint: Minimum Number of Arrows to Burst Balloons

Sort by end. An arrow at 2 bursts both [1, 2] and [2, 3], so you need a new arrow only when start > prev_end. Shoot at the end of the earliest-ending balloon: that arrow still hits every balloon that has started by then, and no other position hits more of the rest.

Hint: Remove Covered Intervals

Sort on (start, -end) so the big umbrella comes first. An interval is not covered when its end is larger than every end seen before it.

Hint: Partition Labels

The intervals are hidden. Each character spans from its first to its last occurrence. In one pass, extend the current part's end to last[c] for every character you see, and close the part when the index reaches that end.

Hint: Maximum Length of Pair Chain

This is the sort-by-end greedy again. Read the problem to see whether touching pairs can chain.

Hint: Maximum Profit in Job Scheduling

A greedy pass is not enough, because jobs have weights. Sort by end, then run a DP over jobs. Binary search finds the last job that ends before the current one starts.

Hint: Data Stream as Disjoint Intervals

Values arrive one at a time, so you cannot sort once. Keep the intervals in a sorted structure and merge each new value with its neighbors.

Hint: Huge coordinates, few intervals

When coordinates reach $10^9$ but there are only about $10^3$ intervals, use coordinate compression. Map the distinct endpoints to 0, 1, 2, ... so an array or a Fenwick tree can index them.

Hint: Meeting Rooms

Sort by start time. If any meeting starts before the previous one ends, a person can't attend all of them.

Key takeaways#

The sort key is the whole problem: start to merge, end to schedule, (start, -end) for covers.
After sorting, one pass with a single "previous end" variable is usually enough.
Earliest finish first is optimal because it leaves the most room for the rest.
Check whether touching endpoints overlap; it flips > and >=.
Depth and capacity questions are a line sweep, not a sort-key greedy.

Core idea#

Most interval problems depend on the sort key. With the right key, one pass with a single "previous end" variable solves them.

Pick the key#

Goal	Sort key
Merge, or insert a new interval	Start
Max non-overlapping, or min removals	End
Is it covered?	`(start, -end)`
Max depth or capacity	Events: line sweep
Intersect two sorted lists	Two pointers; advance the earlier end

Key points#

Sort by start to connect intervals as they arrive. Extend with end = max(end, next_end).
Sort by end to fit the most. The earliest finish leaves the most room.
(start, -end) puts the big umbrella first among equal starts.
Non-overlapping Intervals: touching is fine, so keep when start >= prev_end. Answer is n minus kept.
Min Arrows: touching bursts both, so a new arrow is needed when start > prev_end.
Partition Labels: extend the part's end to last[c]; close it when the index reaches that end.
Job Scheduling needs sort by end, DP and binary search.

Template#

sort intervals by the chosen key
prev_end = minus infinity
for each (start, end) in intervals:
    if start does not overlap prev_end:   # strict or not
        start a new group (keep, count, or shoot)
        prev_end = end
    else:
        handle the overlap (extend, skip, or drop)
        prev_end = the end the rule keeps

Pitfalls#

Sorting by start for max non-overlapping. One long early interval blocks many short ones.
Strict vs non-strict. Touching endpoints flip > and >=. Check the examples.
end = next_end when merging. Use max, or a nested interval shrinks the end.
Sorting covers by -end alone. Sort on (start, -end).

Say it in an interview#

"Start to merge, end to schedule, start then end descending for covers."
"Earliest finish first is optimal because it leaves the most room for the rest."