📅 Greedy & Intervals
Make the locally best move (usually after sorting), and make sure an exchange argument says it never hurts.
Recognize the pattern
"Maximum / minimum number of ..." and sorting by one key makes the next choice obvious → greedy: sort + one pass
Best contiguous subarray sum → Kadane: cur = max(x, cur + x)
Jump array, "can you reach the end / fewest jumps" → track the farthest reach (BFS levels for jump count)
Overlapping ranges to combine (merge, insert, cover) → sort by start, extend the last group
Keep the most non-overlapping / remove the fewest / arrows to burst → sort by end, keep what starts after the last end
"How many at the same time" (rooms, platforms, peak load) → sweep line of +1/-1 events or a min-heap of end times
A small counterexample breaks your greedy (coins like [1, 3, 4]) → switch to DP
Greedy recipe & proof
- Decide what "best next move" means (often: smallest, earliest-ending, closest).
- Sort so that move is always at the front.
- One pass: take it if it's allowed, else skip.
- Prove it with an exchange argument: swapping an optimal answer's choice for greedy's never makes it worse. Or break it with a 3-item counterexample and use DP instead.
Kadane (max subarray sum)
def max_subarray(nums: list[int]) -> int:
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x) # extend or restart
best = max(best, cur)
return best
Reach & jump levels
def can_jump(nums: list[int]) -> bool:
reach = 0
for i, step in enumerate(nums):
if i > reach:
return False
reach = max(reach, i + step)
return True
def min_jumps(nums: list[int]) -> int:
jumps = end = far = 0
for i in range(len(nums) - 1):
far = max(far, i + nums[i])
if i == end: # leave this level
jumps += 1
end = far
return jumps
Merge (sort by start)
def merge(ivs: list[list[int]]) -> list[list[int]]:
out: list[list[int]] = []
for s, e in sorted(ivs):
if out and s <= out[-1][1]: # overlap
out[-1][1] = max(out[-1][1], e)
else:
out.append([s, e])
return out
Max non-overlapping (sort by end)
def max_non_overlapping(ivs: list[list[int]]) -> int:
kept, last_end = 0, float("-inf")
for s, e in sorted(ivs, key=lambda iv: iv[1]):
if s >= last_end: # > if touching clashes
kept += 1
last_end = e
return kept # removals = len(ivs) - kept
Sweep line / min-heap (peak overlap)
import heapq
def peak_overlap(ivs: list[list[int]]) -> int:
events = []
for s, e in ivs:
events += [(s, 1), (e, -1)]
events.sort() # (t, -1) before (t, +1)
cur = best = 0
for _, d in events:
cur += d
best = max(best, cur)
return best
def min_rooms(ivs: list[list[int]]) -> int:
ends: list[int] = [] # end times in use
for s, e in sorted(ivs):
if ends and ends[0] <= s:
heapq.heapreplace(ends, e)
else:
heapq.heappush(ends, e)
return len(ends)
Operation costs
| Operation | Time | Space |
|---|---|---|
| Sort + greedy pass | O(n log n) | O(1)–O(n) |
| Kadane / reach scan | O(n) | O(1) |
| Merge intervals | O(n log n) | O(n) |
| Insert into sorted intervals | O(n) | O(n) |
| Sweep line (2n events) | O(n log n) | O(n) |
| Min-heap of end times | O(n log n) | O(n) |
Watch for
Trusting greedy without a proof: coin change with [1, 3, 4] (amount 6) needs DP.
Kadane starting at 0 returns 0 for all-negative input; start from nums[0].
Sorting by start when choosing the most non-overlapping intervals; sort by end.
Touching intervals: decide from the statement whether [1, 2] and [2, 3] overlap (<= vs <).
Merging without max(): [1, 10] then [2, 3] must stay [1, 10].
Sweep line ties: for half-open meetings process -1 before +1 at the same time.