Question Bank
Greedy Algorithms Warm-Up
Difficulty: Easy
Identify when a greedy choice is correct and when it fails. Drills cover activity selection, coin change with canonical denominations, and Huffman intuition.
Greedy Algorithms Warm-Up
Identify when a greedy choice is correct and when it fails. Drills cover activity selection, coin change with canonical denominations, and Huffman intuition.
728 views
13
Implement activity selection: given a list of (start, end) intervals, return the maximum number of non-overlapping intervals you can pick.
Examples
Example 1:
Input: intervals = [(1, 3), (2, 4), (3, 5), (0, 6), (5, 7), (8, 9)]
Output: 4
Explanation: Sort by end: [(1, 3), (2, 4), (3, 5), (5, 7), (0, 6), (8, 9)]. Accept (1, 3); skip (2, 4); accept (3, 5); accept (5, 7); skip (0, 6); accept (8, 9). 4 picks total.Why does the greedy 'take the largest coin that fits' work for US denominations [1, 5, 10, 25] but fail for [1, 3, 4] when making change for 6?
Implement jump_game(nums) from LeetCode: nums[i] is the max jump length from index i; return True if you can reach the last index.
Examples
Example 1:
Input: nums = [2, 3, 1, 1, 4]
Output: True
Explanation: reach updates as 2, 4, 4, 4, 8. Index never exceeds reach, and reach hits the last index. Greedy is safe because being able to reach any earlier index implies being able to reach every index in [0, reach].Example 2:
Input: nums = [3, 2, 1, 0, 4]
Output: False
Explanation: reach = 3 after index 0, never grows past 3. Index 4 is beyond reach, so the function returns False at the moment i exceeds reach.When does a greedy algorithm need an 'exchange argument' proof, and what does that proof look like in one paragraph?