What you will learn
- Sorting by start versus sorting by end, and when each is right.
- Merging, counting overlaps and scheduling with a heap.
- How to argue a greedy choice is safe.
Signals
- Input is a list of
[start, end]pairs: meetings, bookings, ranges. - “Merge”, “insert”, “overlap”, “minimum rooms”, “maximum non-overlapping”.
- For greedy in general: a locally best choice that never needs undoing (“reach as far as possible”, “finish earliest”).
Code
"""Intervals and greedy: merge, minimum removals, meeting rooms, jump game."""
import heapq
def merge(intervals):
out = []
for start, end in sorted(intervals):
if out and start <= out[-1][1]:
out[-1][1] = max(out[-1][1], end) # overlaps the last one: extend it
else:
out.append([start, end])
return out
def min_removals_to_avoid_overlap(intervals):
"""Greedy: keep the interval that ends earliest, it leaves the most room."""
removed, end = 0, float("-inf")
for s, e in sorted(intervals, key=lambda iv: iv[1]):
if s >= end:
end = e
else:
removed += 1
return removed
def meeting_rooms(intervals):
ends = [] # min-heap of end times of rooms in use
for s, e in sorted(intervals):
if ends and ends[0] <= s:
heapq.heapreplace(ends, e) # reuse the room that frees up first
else:
heapq.heappush(ends, e)
return len(ends)
def can_jump(nums):
reach = 0
for i, step in enumerate(nums):
if i > reach:
return False
reach = max(reach, i + step)
return True
if __name__ == "__main__":
print(merge([[1, 3], [8, 10], [2, 6], [15, 18], [17, 20]]))
print(min_removals_to_avoid_overlap([[1, 2], [2, 3], [3, 4], [1, 3]]))
print(meeting_rooms([[0, 30], [5, 10], [15, 20]]), meeting_rooms([[7, 10], [2, 4]]))
print(can_jump([2, 3, 1, 1, 4]), can_jump([3, 2, 1, 0, 4]))
Output:
[[1, 6], [8, 10], [15, 20]]
1
2 1
True False
- Merge: sort by start; each interval either overlaps the last merged one (extend its end) or starts a new one.
- Minimum removals: sort by end and keep every interval that starts after the last kept one ends. Finishing earliest leaves the most room for the rest; this is the classic activity-selection argument.
- Meeting rooms: sort by start, keep a min-heap of end times. If the earliest-ending room is free by this start, reuse it; otherwise open a new room. The heap size is the answer.
- Jump game: track the furthest reachable index; if you ever stand beyond it, you’re stuck.
Proving a greedy choice
A short exchange argument is usually enough: take any optimal solution; if it doesn’t use the greedy choice, swap the greedy choice in and show the solution stays valid and no worse. For activity selection: replacing the optimal set’s first interval with the earliest-ending interval can’t create an overlap, since it ends no later.
If you can’t find such an argument, the problem may need dynamic programming instead (for example coin change with arbitrary denominations).
Practise: interval problems and greedy problems.
Key takeaways
- Sort by start to merge or to allocate rooms; sort by end to maximise non-overlapping intervals.
- A min-heap of end times counts concurrent intervals.
- Justify greedy with an exchange argument; if it fails, consider DP.
Exercises
- Insert a new interval into a sorted, non-overlapping list and merge as needed.
- Minimum number of arrows to burst balloons (LeetCode 452).
- Jump game II: minimum number of jumps to reach the end, greedily by levels.
Quiz
- Why sort by end time for “minimum removals to avoid overlap”?
- What does the heap size represent in meeting rooms?
- What is an exchange argument?
Show answers
- Keeping the interval that ends earliest leaves the most time for the remaining intervals, which maximises how many can be kept.
- The number of meetings running at the same time at that point, which is the number of rooms needed.
- A proof that you can swap the greedy choice into any optimal solution without making it worse, so greedy is optimal.