An interval is a pair [start, end]. Interval problems — merging overlaps, scheduling meetings, finding free time — almost always begin by sorting the intervals (usually by start), then sweeping through them once. For repeated range sums, a prefix-sum or difference array is the tool.
Sort, then sweep
Once intervals are sorted by start time, a single left-to-right pass can merge overlaps, count concurrent events, or pick the most non-overlapping ones. Two intervals overlap when the next one starts before the current one ends.
Merge overlapping intervals
sort intervals by start
result = [ intervals[0] ]
for each iv in intervals[1..]:
last = result[-1]
if iv.start <= last.end: // overlap
last.end = max(last.end, iv.end)
else:
result.append(iv)
return resultO(n log n)→O(n)
The sort dominates; the sweep is O(n).
⚡ The edge
- Almost every interval problem starts by sorting — by start to merge, by end to schedule the most non-overlapping activities.
- For many range-sum queries on a fixed array, a prefix-sum answers each in O(1); for range updates, a difference array applies each in O(1).
Worked example
Merge the intervals [1,3], [2,6], [8,10], [15,18].
- Sorted by start (already sorted). Take [1,3]; the next [2,6] starts at 2 ≤ 3, so they overlap — merge into [1,6].
- [8,10] starts after 6, so it's separate; [15,18] starts after 10, also separate.
- Result: [1,6], [8,10], [15,18].
Answer: [1,6], [8,10], [15,18]
Worked example
What is the minimum number of meeting rooms for meetings [0,30], [5,10], [15,20]?
- The minimum rooms equals the maximum number of meetings happening at the same time.
- [0,30] overlaps with [5,10] (two at once), and also with [15,20] (two at once), but [5,10] and [15,20] don't overlap each other.
- The peak concurrency is 2, so two rooms suffice.
Answer: 2 rooms
⚠ Watch out
- Decide whether endpoints are inclusive: does [1,2] overlap [2,3]? Define 'touching' before coding.
- Sort by the right key — by start to merge, by end for activity selection.
- Mutating the last interval's end while iterating is fine, but always compare against the merged end, not the original.