Greedy and Intervals Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes the four lessons. For each problem, first name the rule, then ask what could break it, then write the code and state the cost.
Pick the key, then sort
Most greedy problems start with a sort. Finish time suits the most bookings, start time suits merging and rooms, and profit suits jobs with deadlines.
bookings = [(1, 4), (3, 5), (0, 6), (5, 7)]bookings.sort(key=lambda b: b[1])print(bookings)Example 1 · Merge, then total the covered time
ranges = [[5, 8], [1, 3], [2, 4], [7, 10]]merged = []for start, end in sorted(ranges): if merged and start <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], end) else: merged.append([start, end])print(merged, sum(e - s for s, e in merged))[[1, 4], [5, 10]] 8
What this code does
- The ranges merge into [1, 4] and [5, 10]. The covered time is 3 + 5 = 8.
- Sorting makes it O(n log n).
Example 2 · Most bookings without a clash
bookings = [(1, 3), (2, 5), (4, 6), (6, 8), (5, 9)]count, last_end = 0, 0for start, end in sorted(bookings, key=lambda b: b[1]): if start >= last_end: count += 1 last_end = endprint(count)3
What this code does
- Sorted by end, the scan takes (1, 3), (4, 6) and (6, 8).
- Earliest finish leaves the most room for later bookings.
Sorting is O(n log n). After it, one scan keeps the greedy state.
Carry one value through one pass
Reach problems need no sort. The farthest reach, a running tank or the lowest price so far is the one value that tells you when the plan breaks.
def can_reach_end(jumps): reach = 0 for i, step in enumerate(jumps): if i > reach: return False reach = max(reach, i + step) return True
print(can_reach_end([1, 1, 0, 2]))It is O(n) time and O(1) space.
Test the rule before you trust it
If a rule feels too simple, try it on a tiny input that tries to break it. Coins 1, 3 and 4 beat largest-first, while notes of 100, 50, 20, 10, 5 and 1 do not.
Example 3 · Where does a wrong rule fail?
coins = [1, 3, 4]amount = 6greedy = 0left = amountfor coin in sorted(coins, reverse=True): greedy += left // coin left %= coinprint(greedy, "but 3 + 3 uses 2")3 but 3 + 3 uses 2
What this code does
- Largest-first picks 4 and then two 1s. The best answer uses two 3s.
- This is why dynamic programming is needed for general coin sets.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Merge [[1, 5], [2, 3], [6, 7], [7, 9]] and print the result.
[[1, 5], [6, 9]]
Exercise 2· Easy
Meetings are [(1, 2), (2, 3), (3, 4)]. Print True if one person can attend all of them, where a meeting may start when the previous one ends.
True
Exercise 3· Easy
Prices are [8, 3, 10, 2, 9]. Print the best profit from one buy and one later sell.
7
Exercise 4· Medium
Bookings are [(0, 5), (1, 2), (3, 4), (4, 7)]. Print the largest number of non-overlapping bookings.
3
Exercise 5· Medium
Meetings are [(0, 10), (2, 5), (6, 8), (9, 12)]. Print the number of rooms needed.
2
Exercise 6· Medium
Insert [2, 6] into [[1, 2], [4, 5], [7, 8]] and print the list.
[[1, 6], [7, 8]]
Exercise 7· Medium
Jump lengths are [1, 3, 1, 1, 2, 1]. Print the fewest jumps to the last index.
3
Exercise 8· Hard
Gas is [4, 1, 2, 5] and cost is [3, 4, 2, 3]. Print the start index that completes the ring, or -1.
2
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Greedy and Intervals