Master the greedy choice property where locally optimal decisions lead to globally optimal solutions. Learn when greedy works, when it fails, and classic patterns including activity selection, interval scheduling, and jump game variants.
A problem exhibits the greedy choice property when a sequence of locally optimal choices yields a globally optimal solution. Understanding when and why greedy works—and when it fails—is essential for algorithm design.
Definition: At each step, make the locally optimal choice (often the "best" by some metric: minimum, maximum, earliest, latest). If these choices combine to form a globally optimal solution, the problem is greedy-solvable.
When it works: Problems with optimal substructure where future choices don't invalidate past decisions. Example: Activity selection (pick earliest-ending activities greedily).
When it fails: Problems where greedy decisions create constraints that block better global solutions. Example: Longest increasing subsequence (greedy pick of largest elements fails).
Many greedy problems require sorting first. Sort by different keys depending on the problem:
Interval Scheduling: Select maximum number of non-overlapping intervals. Greedy: sort by end time, pick earliest-ending intervals.
Jump Games: Can you reach the end? Track maximum reachable index at each position. Greedy: always jump to maximum reachable position.
Gap Filling: Schedule tasks with gaps between them. Greedy: sort by frequency/deadline, fill largest gaps with most-frequent tasks.
// Template: Activity Selection (Sort + Greedy) public int ActivitySelection(int[] starts, int[] ends) { int n = starts.Length; var activities = new int[n]; for (int i = 0; i < n; i++) activities[i] = i; // Sort by end time System.Array.Sort(activities, (a, b) => ends[a].CompareTo(ends[b])); int count = 0; int lastEnd = 0; foreach (int i in activities) { if (starts[i] >= lastEnd) { count++; lastEnd = ends[i]; } } return count; }
// Template: Jump Game (Track Maximum Reachable) public bool CanReachEnd(int[] nums) { int maxReach = 0; for (int i = 0; i < nums.Length; i++) { if (i > maxReach) return false; maxReach = Math.Max(maxReach, i + nums[i]); } return true; }
You are given an array prices where prices[i] is the price of a stock on day i. You may buy and sell the stock, but only once. Return the maximum profit. If no profit is possible, return 0.
public int MaxProfit(int[] prices) { if (prices == null || prices.Length < 2) return 0; int minPrice = prices[0]; int maxProfit = 0; for (int i = 1; i < prices.Length; i++) { int profit = prices[i] - minPrice; maxProfit = Math.Max(maxProfit, profit); minPrice = Math.Min(minPrice, prices[i]); } return maxProfit; }
prices = [7, 1, 5, 3, 6, 4]
Output: 5 (buy at 1, sell at 6)
You have an array of rope lengths. You need to tie them together to create a rope of at least length K. When you tie two ropes together, the resulting length is the sum of both. Find the minimum number of ropes needed.
public int TieRopes(int[] lengths, int K) { if (lengths == null || lengths.Length == 0) return -1; System.Array.Sort(lengths, (a, b) => b.CompareTo(a)); // Descending int sum = 0; int count = 0; foreach (int length in lengths) { sum += length; count++; if (sum >= K) return count; } return -1; // Cannot reach K }
lengths = [4, 3, 2, 6], K = 10
Given an array of intervals (each with start and end), find the maximum number of non-overlapping intervals you can select.
public int MaxNonoverlappingSegments(int[] A, int[] B) { int n = A.Length; var intervals = new int[n]; for (int i = 0; i < n; i++) intervals[i] = i; // Sort by end time (B[i]) System.Array.Sort(intervals, (i, j) => B[i].CompareTo(B[j])); int count = 0; int lastEnd = int.MinValue; foreach (int i in intervals) { if (A[i] > lastEnd) { count++; lastEnd = B[i]; } } return count; }
A = [1, 3, 7, 9, 9], B = [5, 6, 6, 9, 10]
Intervals: [1,5], [3,6], [7,6], [9,9], [9,10]
Sorted by end: [7,6], [1,5], [3,6], [9,9], [9,10]
Output: 2
Given an array nums where nums[i] is the maximum jump length from index i, return true if you can reach the last index.
public bool CanJump(int[] nums) { int maxReach = 0; for (int i = 0; i < nums.Length; i++) { if (i > maxReach) return false; // Can't reach this index maxReach = Math.Max(maxReach, i + nums[i]); if (maxReach >= nums.Length - 1) return true; } return false; }
nums = [2, 3, 1, 1, 4] (last index = 4)
nums = [3, 2, 1, 0, 4]
Given an array where each element is max jump length, return the minimum jumps to reach the last index. Guaranteed reachable from index 0.
public int Jump(int[] nums) { if (nums.Length <= 1) return 0; int jumps = 0; int currentEnd = 0; // End of current jump's range int nextEnd = 0; // Farthest we can reach from current range for (int i = 0; i < nums.Length - 1; i++) { nextEnd = Math.Max(nextEnd, i + nums[i]); if (i == currentEnd) { jumps++; currentEnd = nextEnd; } } return jumps; }
nums = [2, 3, 1, 1, 4]
Output: 2
You have a circular route with n stations. At each station i, you can get gas[i] gas and spend cost[i] gas to reach the next station. Find the starting station index such that you can travel the entire loop. If impossible, return -1.
public int CanCompleteCircuit(int[] gas, int[] cost) { long totalGas = 0, totalCost = 0; foreach (int g in gas) totalGas += g; foreach (int c in cost) totalCost += c; if (totalGas < totalCost) return -1; int start = 0; long currentGas = 0; for (int i = 0; i < gas.Length; i++) { currentGas += gas[i] - cost[i]; if (currentGas < 0) { start = i + 1; currentGas = 0; } } return start; }
gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Given prices for multiple days, find the max profit with unlimited transactions. You must sell before buying again.
public int MaxProfitMultiple(int[] prices) { int profit = 0; for (int i = 0; i < prices.Length - 1; i++) { int gain = prices[i + 1] - prices[i]; if (gain > 0) { profit += gain; } } return profit; }
prices = [7, 1, 5, 3, 6, 4]
You have children with greed factors and cookies with sizes. A child is satisfied if cookie size ≥ greed factor. Maximize the number of satisfied children (each cookie to one child).
public int FindContentChildren(int[] g, int[] s) { System.Array.Sort(g); // Children greed factors System.Array.Sort(s); // Cookie sizes int childIdx = 0, cookieIdx = 0; while (childIdx < g.Length && cookieIdx < s.Length) { if (s[cookieIdx] >= g[childIdx]) { childIdx++; // Child satisfied, move to next child } cookieIdx++; // Move to next cookie } return childIdx; }
g = [1, 2, 3], s = [1, 1]
Output: 1
Given a list of intervals, return the minimum number of intervals to remove so that the remaining intervals don't overlap.
public int EraseOverlapIntervals(int[][] intervals) { if (intervals.Length <= 1) return 0; System.Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1])); // Sort by end int count = 1; int lastEnd = intervals[0][1]; for (int i = 1; i < intervals.Length; i++) { if (intervals[i][0] >= lastEnd) { count++; lastEnd = intervals[i][1]; } } return intervals.Length - count; }
intervals = [[1,2], [2,3], [3,4], [1,3]]
Output: 4 - 3 = 1 (remove 1 interval)
Balloons are represented by [xstart, xend]. An arrow shot at coordinate x bursts all balloons where xstart ≤ x ≤ xend. Find minimum arrows needed.
public int FindMinArrowShots(int[][] points) { if (points.Length == 0) return 0; System.Array.Sort(points, (a, b) => { // Handle overflow: use long for comparison long diff = (long)a[1] - (long)b[1]; if (diff < 0) return -1; if (diff > 0) return 1; return 0; }); int arrows = 1; long lastEnd = points[0][1]; for (int i = 1; i < points.Length; i++) { if (points[i][0] > lastEnd) { arrows++; lastEnd = points[i][1]; } } return arrows; }
points = [[10,16], [2,8], [1,6], [7,12]]
Output: 2
long for comparisonsYou have tasks represented as characters (same task type requires cooldown n between executions). Return the minimum time units to execute all tasks.
public int LeastInterval(char[] tasks, int n) { // Count frequency of each task int[] freq = new int[26]; int maxFreq = 0; foreach (char task in tasks) { freq[task - 'A']++; maxFreq = Math.Max(maxFreq, freq[task - 'A']); } // Count tasks with max frequency int countMaxFreq = 0; for (int i = 0; i < 26; i++) { if (freq[i] == maxFreq) countMaxFreq++; } // Formula: (maxFreq - 1) * (n + 1) + countMaxFreq int minTime = (maxFreq - 1) * (n + 1) + countMaxFreq; // At least tasks.Length time needed if many unique tasks return Math.Max(minTime, tasks.Length); }
tasks = ['A', 'A', 'A', 'B', 'B', 'C'], n = 2
Output: 8 (actual schedule may need gaps filled)
Given a string, partition it such that each letter appears in at most one part. Return the sizes of these partitions.
public IList<int> PartitionLabels(string s) { // Record last occurrence of each character int[] lastOccur = new int[26]; for (int i = 0; i < s.Length; i++) { lastOccur[s[i] - 'a'] = i; } var result = new List<int>(); int start = 0, maxEnd = 0; for (int i = 0; i < s.Length; i++) { maxEnd = Math.Max(maxEnd, lastOccur[s[i] - 'a']); if (i == maxEnd) { // Partition here result.Add(i - start + 1); start = i + 1; } } return result; }
s = "ababcbacaddefegdehijhijk"
Output: [9, 7, 8]