[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":89,"_73":90,"_35":91},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",46,"title","Greedy Algorithms","slug","algorithms-part-19-greedy-algorithms","excerpt","Understand when greedy works and when it fails. Solve activity selection, Huffman coding, fractional knapsack, and job scheduling with proven correctness.","# Part 19: Greedy Algorithms - Making Locally Optimal Choices\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Time to Read | 35 minutes |\n| Prerequisites | Part 1 (Algorithm Analysis), Part 16 (DP basics) |\n| Key Concepts | Greedy Choice, Activity Selection, Huffman, Scheduling |\n| Difficulty | ⭐⭐⭐ (Intermediate) |\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ GREEDY ALGORITHMS │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ THE GREEDY APPROACH │\n│ ┌─────────────────────────────────────────────────────────┐ │\n│ │ │ │\n│ │ At each step, make the locally optimal choice │ │\n│ │ Hope it leads to globally optimal solution │ │\n│ │ │ │\n│ │ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │ │\n│ │ │Start│───→│Best │───→│Best │───→│Goal │ │ │\n│ │ │ │ │local│ │local│ │ │ │ │\n│ │ └─────┘ └─────┘ └─────┘ └─────┘ │ │\n│ │ │ │\n│ │Works when: Greedy choice property + Optimal substructure│ │\n│ │ │ │\n│ └─────────────────────────────────────────────────────────┘ │\n│ │\n│ CLASSIC PROBLEMS │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ Activity Select │ │ Huffman Coding │ │\n│ │ ─────────────── │ │ ─────────────── │ │\n│ │ Max activities │ │ Optimal prefix │ │\n│ │ without overlap │ │ codes │ │\n│ └─────────────────┘ └─────────────────┘ │\n│ │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ Fractional │ │ Job Scheduling │ │\n│ │ Knapsack │ │ ─────────────── │ │\n│ │ ─────────────── │ │ Minimize │ │\n│ │ Max value with │ │ penalties │ │\n│ │ fractions │ │ │ │\n│ └─────────────────┘ └─────────────────┘ │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🎯 What You'll Learn\n\nAfter completing this article, you will be able to:\n\n1. **Identify greedy problems**: Recognize when greedy works\n2. **Prove correctness**: Exchange argument and greedy stays ahead\n3. **Solve classic problems**: Activity selection, Huffman, scheduling\n4. **Avoid pitfalls**: Know when greedy fails\n\n---\n\n## 🔥 Production Story: The Task Scheduler Optimization\n\nA cloud platform needed to schedule thousands of tasks to minimize total completion time.\n\n### The Problem\n\n```java\n// ❌ Naive: Try all orderings (n! possibilities)\npublic class NaiveScheduler {\n public int minTotalCompletionTime(int[] taskDurations) {\n // Generate all permutations...\n // Calculate completion time for each...\n // Return minimum...\n // IMPOSSIBLE for n > 10\n return -1;\n }\n}\n```\n\n### The Solution: Shortest Job First\n\n```java\n// ✅ Greedy: Shortest Job First (SJF)\npublic class GreedyScheduler {\n public int minTotalCompletionTime(int[] taskDurations) {\n // Sort by duration (shortest first)\n Arrays.sort(taskDurations);\n\n int totalCompletionTime = 0;\n int currentTime = 0;\n\n for (int duration : taskDurations) {\n currentTime += duration;\n totalCompletionTime += currentTime;\n }\n\n return totalCompletionTime;\n }\n}\n\n// Example:\n// Tasks: [3, 1, 2]\n//\n// Greedy (sorted: [1, 2, 3]):\n// Task 1: completes at 1, total = 1\n// Task 2: completes at 1+2=3, total = 1+3=4\n// Task 3: completes at 3+3=6, total = 4+6=10\n//\n// Non-optimal [3, 1, 2]:\n// Task 3: completes at 3, total = 3\n// Task 1: completes at 4, total = 3+4=7\n// Task 2: completes at 6, total = 7+6=13\n```\n\n### Why It Works (Exchange Argument)\n\n```\nIf tasks aren't in SJF order, we can improve by swapping adjacent jobs:\n\nBefore swap: [..., A, B, ...] where duration(A) > duration(B)\n A completes at time t\n B completes at time t + duration(B)\n\nAfter swap: [..., B, A, ...]\n B completes at time t - duration(A) + duration(B) = t'\n A completes at time t\n\nSince duration(B) < duration(A):\n- B's completion time decreased\n- A's completion time stayed same\n- Total improved!\n\nTherefore, SJF order is optimal.\n```\n\n---\n\n## 🧠 Mental Model: The Greedy Framework\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ GREEDY ALGORITHM FRAMEWORK │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ STEP 1: Identify the greedy choice │\n│ ┌─────────────────────────────────────────────────────────┐ │\n│ │ What's the \"best\" item to pick first? │ │\n│ │ - Largest? Smallest? Earliest finish? Best ratio? │ │\n│ └─────────────────────────────────────────────────────────┘ │\n│ │\n│ STEP 2: Prove greedy choice is safe │\n│ ┌─────────────────────────────────────────────────────────┐ │\n│ │ Show: There exists an optimal solution that includes │ │\n│ │ our greedy choice │ │\n│ │ │ │\n│ │ Methods: │ │\n│ │ - Exchange argument │ │\n│ │ - Greedy stays ahead │ │\n│ │ - Structural argument │ │\n│ └─────────────────────────────────────────────────────────┘ │\n│ │\n│ STEP 3: Prove optimal substructure │\n│ ┌─────────────────────────────────────────────────────────┐ │\n│ │ After making greedy choice, remaining problem is │ │\n│ │ smaller instance of same problem │ │\n│ └─────────────────────────────────────────────────────────┘ │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🔬 Deep Dive: Activity Selection\n\n### The Problem\n\nGiven activities with start and end times, select maximum non-overlapping activities.\n\n```java\npublic class ActivitySelection {\n public List selectActivities(int[][] activities) {\n // Sort by end time (greedy choice: earliest finish first)\n Arrays.sort(activities, (a, b) -> a[1] - b[1]);\n\n List selected = new ArrayList<>();\n int lastEnd = 0;\n\n for (int[] activity : activities) {\n if (activity[0] >= lastEnd) { // No overlap\n selected.add(activity);\n lastEnd = activity[1];\n }\n }\n\n return selected;\n }\n}\n```\n\n### Why Earliest Finish First Works\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ ACTIVITY SELECTION PROOF │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Claim: Greedy choice (earliest finish) is always safe │\n│ │\n│ Proof by exchange: │\n│ Let OPT be any optimal solution │\n│ Let a₁ be the activity with earliest finish time │\n│ Let a_first be the first activity in OPT │\n│ │\n│ If a₁ = a_first: Done! Greedy matches OPT │\n│ │\n│ If a₁ ≠ a_first: │\n│ - a₁ finishes no later than a_first (earliest finish) │\n│ - Replace a_first with a₁ in OPT │\n│ - No new conflicts (a₁ ends earlier) │\n│ - Same size, still valid → OPT' is optimal with a₁ │\n│ │\n│ Timeline: │\n│ a₁: |-----| │\n│ a_first:|--------| │\n│ next: |-----| │\n│ │\n│ Swapping a_first → a₁ can only add more room for next │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Weighted Activity Selection\n\nWhen activities have weights, greedy doesn't work - need DP:\n\n```java\npublic class WeightedActivitySelection {\n public int maxWeight(int[][] activities, int[] weights) {\n int n = activities.length;\n\n // Sort by end time\n Integer[] indices = new Integer[n];\n for (int i = 0; i < n; i++) indices[i] = i;\n Arrays.sort(indices, (a, b) -> activities[a][1] - activities[b][1]);\n\n // p[i] = last compatible activity before i\n int[] p = new int[n];\n for (int i = 0; i < n; i++) {\n p[i] = -1;\n for (int j = i - 1; j >= 0; j--) {\n if (activities[indices[j]][1] <= activities[indices[i]][0]) {\n p[i] = j;\n break;\n }\n }\n }\n\n // dp[i] = max weight using activities 0..i\n int[] dp = new int[n];\n dp[0] = weights[indices[0]];\n\n for (int i = 1; i < n; i++) {\n int include = weights[indices[i]];\n if (p[i] != -1) include += dp[p[i]];\n\n dp[i] = Math.max(dp[i-1], include);\n }\n\n return dp[n-1];\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Huffman Coding\n\n### The Problem\n\nCreate optimal prefix-free codes for data compression.\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ HUFFMAN CODING │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Characters: a(45%), b(13%), c(12%), d(16%), e(9%), f(5%) │\n│ │\n│ Fixed-length: 3 bits each → 3 × 100 = 300 bits │\n│ │\n│ Huffman tree: │\n│ (100) │\n│ / \\ │\n│ (55) a(45) │\n│ / \\ 0 │\n│ (25) (30) │\n│ / \\ / \\ │\n│ c(12) b(13) d(16) (14) │\n│ 100 101 110 / \\ │\n│ f(5) e(9) │\n│ 1110 1111 │\n│ │\n│ Huffman: 1×45 + 3×13 + 3×12 + 3×16 + 4×9 + 4×5 = 224 bits │\n│ Savings: 25% │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Implementation\n\n```java\npublic class HuffmanCoding {\n static class Node implements Comparable {\n char ch;\n int freq;\n Node left, right;\n\n Node(char ch, int freq) {\n this.ch = ch;\n this.freq = freq;\n }\n\n Node(int freq, Node left, Node right) {\n this.ch = '\\0';\n this.freq = freq;\n this.left = left;\n this.right = right;\n }\n\n boolean isLeaf() {\n return left == null && right == null;\n }\n\n @Override\n public int compareTo(Node other) {\n return this.freq - other.freq;\n }\n }\n\n public Map buildCodes(char[] chars, int[] freqs) {\n // Build min-heap of leaf nodes\n PriorityQueue pq = new PriorityQueue<>();\n for (int i = 0; i < chars.length; i++) {\n pq.offer(new Node(chars[i], freqs[i]));\n }\n\n // Build Huffman tree\n while (pq.size() > 1) {\n Node left = pq.poll();\n Node right = pq.poll();\n Node parent = new Node(left.freq + right.freq, left, right);\n pq.offer(parent);\n }\n\n Node root = pq.poll();\n\n // Generate codes\n Map codes = new HashMap<>();\n generateCodes(root, \"\", codes);\n return codes;\n }\n\n private void generateCodes(Node node, String code, Map codes) {\n if (node == null) return;\n\n if (node.isLeaf()) {\n codes.put(node.ch, code.isEmpty() ? \"0\" : code);\n return;\n }\n\n generateCodes(node.left, code + \"0\", codes);\n generateCodes(node.right, code + \"1\", codes);\n }\n\n public String encode(String text, Map codes) {\n StringBuilder encoded = new StringBuilder();\n for (char c : text.toCharArray()) {\n encoded.append(codes.get(c));\n }\n return encoded.toString();\n }\n\n public String decode(String encoded, Node root) {\n StringBuilder decoded = new StringBuilder();\n Node current = root;\n\n for (char bit : encoded.toCharArray()) {\n current = (bit == '0') ? current.left : current.right;\n\n if (current.isLeaf()) {\n decoded.append(current.ch);\n current = root;\n }\n }\n\n return decoded.toString();\n }\n}\n```\n\n### Why Huffman is Optimal\n\n```\nGreedy choice: Always merge two nodes with smallest frequencies\n\nProof idea:\n1. Optimal tree exists where two lowest-frequency symbols are siblings\n at the deepest level (exchange argument)\n\n2. After merging, we have smaller instance of same problem\n (one fewer symbol, combined frequency)\n\n3. Recursively optimal → globally optimal\n```\n\n---\n\n## 🔬 Deep Dive: Fractional Knapsack\n\n### The Problem\n\nUnlike 0/1 knapsack, we can take fractions of items.\n\n```java\npublic class FractionalKnapsack {\n public double maxValue(int[] weights, int[] values, int capacity) {\n int n = weights.length;\n\n // Create items with value-to-weight ratio\n double[][] items = new double[n][3];\n for (int i = 0; i < n; i++) {\n items[i][0] = weights[i];\n items[i][1] = values[i];\n items[i][2] = (double) values[i] / weights[i]; // Ratio\n }\n\n // Sort by ratio (descending)\n Arrays.sort(items, (a, b) -> Double.compare(b[2], a[2]));\n\n double totalValue = 0;\n int remainingCapacity = capacity;\n\n for (double[] item : items) {\n int weight = (int) item[0];\n double value = item[1];\n\n if (weight <= remainingCapacity) {\n // Take whole item\n totalValue += value;\n remainingCapacity -= weight;\n } else {\n // Take fraction\n totalValue += value * remainingCapacity / weight;\n break; // Knapsack full\n }\n }\n\n return totalValue;\n }\n}\n```\n\n### Comparison with 0/1 Knapsack\n\n```\nItems: weights = [10, 20, 30], values = [60, 100, 120], capacity = 50\n\nRatios: 60/10=6, 100/20=5, 120/30=4\n\nFractional (greedy):\n- Take all of item 1: value=60, remaining=40\n- Take all of item 2: value=60+100=160, remaining=20\n- Take 20/30 of item 3: value=160+120×(20/30)=240\n\n0/1 (DP needed):\n- Take items 2 and 3: value=100+120=220\n\nGreedy gives 240 for fractional, but would give wrong answer for 0/1!\n```\n\n---\n\n## 🔬 Deep Dive: Job Scheduling\n\n### Minimizing Lateness\n\n```java\npublic class JobSchedulingLateness {\n // Jobs with processing times and deadlines\n // Minimize maximum lateness\n\n public int minMaxLateness(int[] processingTime, int[] deadline) {\n int n = processingTime.length;\n\n // Sort by deadline (Earliest Deadline First)\n Integer[] indices = new Integer[n];\n for (int i = 0; i < n; i++) indices[i] = i;\n Arrays.sort(indices, (a, b) -> deadline[a] - deadline[b]);\n\n int currentTime = 0;\n int maxLateness = 0;\n\n for (int i : indices) {\n currentTime += processingTime[i];\n int lateness = currentTime - deadline[i];\n maxLateness = Math.max(maxLateness, lateness);\n }\n\n return maxLateness;\n }\n}\n```\n\n### Job Scheduling with Profits and Deadlines\n\n```java\npublic class JobSchedulingProfit {\n // Each job has: deadline (day by which it must complete) and profit\n // Jobs take 1 unit of time. Maximize total profit.\n\n public int maxProfit(int[] deadlines, int[] profits) {\n int n = deadlines.length;\n\n // Sort jobs by profit (descending)\n Integer[] indices = new Integer[n];\n for (int i = 0; i < n; i++) indices[i] = i;\n Arrays.sort(indices, (a, b) -> profits[b] - profits[a]);\n\n int maxDeadline = Arrays.stream(deadlines).max().getAsInt();\n int[] schedule = new int[maxDeadline + 1];\n Arrays.fill(schedule, -1);\n\n int totalProfit = 0;\n\n for (int idx : indices) {\n int deadline = deadlines[idx];\n int profit = profits[idx];\n\n // Find latest available slot before deadline\n for (int slot = deadline; slot > 0; slot--) {\n if (schedule[slot] == -1) {\n schedule[slot] = idx;\n totalProfit += profit;\n break;\n }\n }\n }\n\n return totalProfit;\n }\n\n // Optimized with Union-Find\n public int maxProfitOptimized(int[] deadlines, int[] profits) {\n int n = deadlines.length;\n int maxDeadline = Arrays.stream(deadlines).max().getAsInt();\n\n // Sort by profit\n Integer[] indices = new Integer[n];\n for (int i = 0; i < n; i++) indices[i] = i;\n Arrays.sort(indices, (a, b) -> profits[b] - profits[a]);\n\n // Union-Find to quickly find available slot\n int[] parent = new int[maxDeadline + 2];\n for (int i = 0; i <= maxDeadline + 1; i++) parent[i] = i;\n\n int totalProfit = 0;\n\n for (int idx : indices) {\n int deadline = Math.min(deadlines[idx], maxDeadline);\n int availableSlot = find(parent, deadline);\n\n if (availableSlot > 0) {\n totalProfit += profits[idx];\n parent[availableSlot] = find(parent, availableSlot - 1);\n }\n }\n\n return totalProfit;\n }\n\n private int find(int[] parent, int x) {\n if (parent[x] != x) {\n parent[x] = find(parent, parent[x]);\n }\n return parent[x];\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: When Greedy Fails\n\n### Coin Change Problem\n\n```java\npublic class CoinChangeGreedy {\n // Greedy works for standard US coins: [1, 5, 10, 25]\n public int coinChangeGreedy(int[] coins, int amount) {\n Arrays.sort(coins);\n int count = 0;\n\n for (int i = coins.length - 1; i >= 0 && amount > 0; i--) {\n count += amount / coins[i];\n amount %= coins[i];\n }\n\n return amount == 0 ? count : -1;\n }\n\n // But fails for some coin systems!\n // coins = [1, 3, 4], amount = 6\n // Greedy: 4 + 1 + 1 = 3 coins\n // Optimal: 3 + 3 = 2 coins\n}\n```\n\n### The Key Difference\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ GREEDY vs DYNAMIC PROGRAMMING │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ GREEDY │\n│ ─────── │\n│ - Makes one choice at each step │\n│ - Never reconsiders choices │\n│ - Works when: greedy choice property holds │\n│ - Time: Usually O(n) or O(n log n) │\n│ │\n│ DYNAMIC PROGRAMMING │\n│ ──────────────────── │\n│ - Considers all choices at each step │\n│ - Stores results for future use │\n│ - Works when: optimal substructure only │\n│ - Time: Usually O(n²) or O(n×k) │\n│ │\n│ Rule of thumb: │\n│ ─────────────── │\n│ 1. Try greedy first (simpler, faster) │\n│ 2. Find counterexample → use DP │\n│ 3. Prove greedy works → keep greedy │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Assuming Greedy Always Works\n\n```java\n// ❌ WRONG: Using greedy for 0/1 knapsack\npublic int knapsackGreedy(int[] weights, int[] values, int capacity) {\n // Sort by value/weight ratio - WRONG for 0/1!\n // ...\n}\n\n// ✅ CORRECT: Use DP for 0/1 knapsack\npublic int knapsackDP(int[] weights, int[] values, int capacity) {\n // DP solution\n}\n```\n\n---\n\n### Mistake 2: Wrong Greedy Criterion\n\n```java\n// ❌ WRONG: Activity selection by start time\nArrays.sort(activities, (a, b) -> a[0] - b[0]); // Wrong!\n\n// ✅ CORRECT: Activity selection by end time\nArrays.sort(activities, (a, b) -> a[1] - b[1]); // Correct!\n```\n\n---\n\n### Mistake 3: Not Handling Ties Properly\n\n```java\n// ❌ WRONG: Inconsistent tie handling\npublic int schedule(int[][] jobs) {\n // What if two jobs have same deadline?\n Arrays.sort(jobs, (a, b) -> a[1] - b[1]);\n // ...\n}\n\n// ✅ CORRECT: Define secondary criterion\npublic int schedule(int[][] jobs) {\n // Break ties by processing time\n Arrays.sort(jobs, (a, b) -> {\n if (a[1] != b[1]) return a[1] - b[1];\n return a[0] - b[0]; // Secondary: shorter jobs first\n });\n // ...\n}\n```\n\n---\n\n## 🐛 Debug This: Activity Selection Bug\n\nThis activity selection has a bug. Can you find it?\n\n```java\npublic List selectActivities(int[][] activities) {\n // Sort by duration (shortest first)\n Arrays.sort(activities, (a, b) -> (a[1] - a[0]) - (b[1] - b[0]));\n\n List selected = new ArrayList<>();\n int lastEnd = 0;\n\n for (int[] activity : activities) {\n if (activity[0] >= lastEnd) {\n selected.add(activity);\n lastEnd = activity[1];\n }\n }\n\n return selected;\n}\n```\n\n

🔍 Click to reveal the bug

\n\n**Bug**: Sorting by duration instead of end time.\n\n```java\n// ❌ BUG: Shortest duration doesn't maximize activities\nArrays.sort(activities, (a, b) -> (a[1] - a[0]) - (b[1] - b[0]));\n\n// ✅ FIX: Sort by end time (earliest finish first)\nArrays.sort(activities, (a, b) -> a[1] - b[1]);\n```\n\n**Counterexample**:\n```\nActivities: [0,10], [1,3], [3,5], [5,7], [7,9]\n\nShortest duration first: [1,3] (len 2), [3,5] (len 2), [5,7] (len 2), [7,9] (len 2), [0,10] (len 10)\nResult: [1,3], [3,5], [5,7], [7,9] = 4 activities ✓\n\nBut consider: [0,2], [1,10], [2,3]\nShortest first: [0,2] (len 2), [2,3] (len 1), [1,10] (len 9)\nOrder: [2,3], [0,2], [1,10]\nResult: [2,3] (can't add [0,2] - overlaps!) = 1 activity\n\nEarliest finish: [0,2], [2,3], [1,10]\nResult: [0,2], [2,3] = 2 activities ✓\n```\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Assign Mice to Holes ⭐⭐\n\nN mice and N holes on a line. Find minimum time for all mice to reach holes (each mouse to one hole).\n\n```java\npublic int assignMice(int[] mice, int[] holes) {\n // Hint: Sort both arrays\n}\n```\n\n---\n\n### Exercise 2: Minimum Platforms ⭐⭐\n\nGiven arrival and departure times of trains, find minimum platforms needed.\n\n```java\npublic int minPlatforms(int[] arrivals, int[] departures) {\n // Hint: Event-based approach\n}\n```\n\n---\n\n### Exercise 3: Gas Station ⭐⭐⭐\n\nN gas stations in a circle. Find starting station to complete the circuit.\n\n```java\npublic int canCompleteCircuit(int[] gas, int[] cost) {\n // Can be solved with greedy\n}\n```\n\n---\n\n### Exercise 4: Jump Game II ⭐⭐⭐\n\nMinimum jumps to reach end. Each position has max jump length.\n\n```java\npublic int jump(int[] nums) {\n // Greedy: always jump to position that allows farthest reach\n}\n```\n\n---\n\n### Exercise 5: Meeting Rooms III ⭐⭐⭐⭐\n\nGiven n rooms and meetings, find which room held most meetings. Meetings go to lowest numbered available room.\n\n```java\npublic int mostBooked(int n, int[][] meetings) {\n // Hint: Use two heaps\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Q1: \"How do you prove a greedy algorithm is correct?\"\n\n**Answer**: Two main techniques:\n\n**1. Exchange Argument**:\n- Take any optimal solution OPT\n- Show we can transform it to match greedy without worsening\n- Usually swap elements to show greedy choice is at least as good\n\n**2. Greedy Stays Ahead**:\n- Define a measure of progress\n- Show greedy solution is always at least as good as any other\n- By induction: if greedy is ahead at step k, it stays ahead at step k+1\n\n**Example for Activity Selection**:\n```\nExchange: If OPT's first activity isn't earliest-finish,\n swap it with earliest-finish activity.\n Result: same or fewer conflicts.\n\nStays ahead: At each step, greedy has at least as many\n activities AND ends no later than any other\n solution with same number of activities.\n```\n\n---\n\n### Q2: \"When should I try greedy vs DP?\"\n\n**Answer**:\n\n**Try Greedy First When**:\n- Problem has \"optimal substructure\"\n- Local choices seem to lead to global optimum\n- You can identify a clear greedy criterion\n\n**Use DP When**:\n- Greedy counterexample exists\n- Need to consider multiple choices\n- Problem has overlapping subproblems\n\n**Quick Test**:\n1. Propose greedy strategy\n2. Try to find counterexample\n3. If found → use DP\n4. If not → try to prove greedy works\n\n---\n\n### Q3: \"Implement interval scheduling with weights.\"\n\n**Answer**:\n\n```java\npublic int weightedIntervalScheduling(int[][] intervals, int[] weights) {\n int n = intervals.length;\n\n // Sort by end time\n Integer[] idx = IntStream.range(0, n).boxed().toArray(Integer[]::new);\n Arrays.sort(idx, (a, b) -> intervals[a][1] - intervals[b][1]);\n\n // Find p[i] = last compatible interval before i\n int[] p = new int[n];\n for (int i = 0; i < n; i++) {\n p[i] = -1;\n for (int j = i - 1; j >= 0; j--) {\n if (intervals[idx[j]][1] <= intervals[idx[i]][0]) {\n p[i] = j;\n break;\n }\n }\n }\n\n // DP\n int[] dp = new int[n];\n dp[0] = weights[idx[0]];\n\n for (int i = 1; i < n; i++) {\n int include = weights[idx[i]] + (p[i] >= 0 ? dp[p[i]] : 0);\n dp[i] = Math.max(dp[i-1], include);\n }\n\n return dp[n-1];\n}\n```\n\nKey insight: Greedy doesn't work with weights. Need DP because taking an interval affects which others we can take.\n\n---\n\n### Q4: \"Design an algorithm for task scheduling with dependencies.\"\n\n**Answer**: Use topological sort + greedy:\n\n```java\npublic int[] scheduleTasks(int n, int[][] dependencies, int[] durations) {\n // Build graph and compute in-degrees\n List> adj = new ArrayList<>();\n int[] inDegree = new int[n];\n for (int i = 0; i < n; i++) adj.add(new ArrayList<>());\n for (int[] dep : dependencies) {\n adj.get(dep[0]).add(dep[1]);\n inDegree[dep[1]]++;\n }\n\n // Priority queue: prefer shorter tasks when multiple available\n PriorityQueue ready = new PriorityQueue<>(\n Comparator.comparingInt(i -> durations[i]));\n\n for (int i = 0; i < n; i++) {\n if (inDegree[i] == 0) ready.offer(i);\n }\n\n List schedule = new ArrayList<>();\n while (!ready.isEmpty()) {\n int task = ready.poll();\n schedule.add(task);\n\n for (int next : adj.get(task)) {\n if (--inDegree[next] == 0) {\n ready.offer(next);\n }\n }\n }\n\n return schedule.stream().mapToInt(i -> i).toArray();\n}\n```\n\n---\n\n### Q5: \"What's the difference between Huffman and Shannon-Fano coding?\"\n\n**Answer**:\n\n| Aspect | Huffman | Shannon-Fano |\n|--------|---------|--------------|\n| Approach | Bottom-up (merge smallest) | Top-down (split into halves) |\n| Optimality | Optimal prefix code | Near-optimal |\n| Construction | Build tree from leaves | Divide symbols recursively |\n| Complexity | O(n log n) | O(n log n) |\n\n**Huffman is always optimal** for symbol-by-symbol coding because:\n1. Merging two smallest frequencies is provably safe\n2. Resulting tree has minimum weighted path length\n\nShannon-Fano can produce suboptimal codes because splitting by frequency doesn't guarantee optimal bit allocation.\n\n---\n\n## 📋 Quick Reference\n\n### Classic Greedy Problems\n\n| Problem | Greedy Criterion | Time |\n|---------|------------------|------|\n| Activity Selection | Earliest finish | O(n log n) |\n| Huffman Coding | Smallest frequencies | O(n log n) |\n| Fractional Knapsack | Best value/weight | O(n log n) |\n| Job Scheduling (lateness) | Earliest deadline | O(n log n) |\n| Minimum Spanning Tree | Smallest edge | O(E log V) |\n| Dijkstra's Algorithm | Closest vertex | O((V+E) log V) |\n\n### When Greedy Fails\n\n| Problem | Why Greedy Fails |\n|---------|------------------|\n| 0/1 Knapsack | Can't take fractions |\n| Coin Change (general) | Skipping a coin might be better |\n| Longest Path | Local longest doesn't give global |\n| Graph Coloring | Greedy can use more colors |\n\n### Proof Techniques\n\n```\nExchange Argument:\n1. Let OPT be optimal solution\n2. If OPT differs from greedy at step k\n3. Show we can swap to match greedy\n4. Solution doesn't worsen → greedy is optimal\n\nGreedy Stays Ahead:\n1. Define measure M (e.g., activities selected)\n2. Show M(greedy, k) ≥ M(any other, k) for all k\n3. By induction, greedy ends up optimal\n```\n\n---\n\n## 🔗 What's Next?\n\nIn **Part 20: Backtracking & Branch and Bound**, we'll explore:\n- Backtracking template\n- N-Queens, Sudoku solver\n- Subset/permutation generation\n- Branch and bound optimization\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| 0 | Full read + Activity Selection | 90 min |\n| 1 | Quick Reference | 10 min |\n| 3 | Implement Huffman | 25 min |\n| 7 | Job scheduling exercises | 20 min |\n| 14 | Debug exercise + proofs | 15 min |\n| 30 | Interview questions | 15 min |\n\n---\n\n**Next**: [Part 20: Backtracking & Branch and Bound →](./algorithms-part-20-backtracking.md)\n\n**Series**: [Algorithms Compendium Index](./algorithms-part-0-series-overview.md)\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.296571Z","createdAt","2026-06-10T07:19:25.297382Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",17,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",19,"author",{"_31":55,"_99":57,"_100":101,"_102":103,"_104":-5,"_105":-5,"_106":-5,"_107":-5,"_108":-5},"category",{"_31":95,"_73":59,"_35":96,"_76":97,"_98":-5},"tags",[79,80,81,82],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":92,"_73":93,"_35":94},{"_31":89,"_73":90,"_35":91},{"_31":86,"_73":87,"_35":88},{"_31":83,"_73":84,"_35":85},199,"Job Scheduling","job-scheduling",198,"Huffman Coding","huffman-coding",196,"Greedy","greedy",197,"Activity Selection","activity-selection",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]