Greedy Algorithm Patterns

1. Activity Selection Problem (Interval Scheduling)

Aspect	Description	Complexity
Pattern	Select maximum number of non-overlapping activities by always choosing the activity that finishes earliest	`O(n log n)`
Key Insight	Sorting by end time and greedily selecting earliest-finishing compatible activity gives optimal solution	Proof by exchange
Approach	Sort intervals by end time, iterate and select if start ≥ last selected end	Single pass after sort
Use Cases	Meeting room scheduling, task scheduling, interval partitioning	Optimal subset

Example: Activity Selection

function activitySelection(activities) {
  // Sort by end time
  activities.sort((a, b) => a[1] - b[1]);
  
  const selected = [activities[0]];
  let lastEnd = activities[0][1];
  
  for (let i = 1; i < activities.length; i++) {
    const [start, end] = activities[i];
    // Select if non-overlapping
    if (start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = end;
    }
  }
  
  return selected;
}

// Example: [[1,3], [2,5], [4,6], [6,8], [5,7], [8,9]]
// After sorting by end: [[1,3], [2,5], [4,6], [5,7], [6,8], [8,9]]
// Selected: [[1,3], [4,6], [6,8], [8,9]]
const activities = [[1,3], [2,5], [4,6], [6,8], [5,7], [8,9]];
console.log(activitySelection(activities)); // 4 activities

Note: Why sort by end time? If we sort by start time or duration, we might select a long activity that blocks many shorter ones. Earliest finish time ensures maximum room for future selections.

2. Jump Game Reachability Problem

Variant	Problem	Greedy Strategy
Jump Game I	Can reach last index from index 0?	Track maximum reachable position, update at each step
Jump Game II	Minimum jumps to reach end	BFS-like approach: jump when current range ends, count levels
Key Insight	At each position, maximize reach; if current position unreachable, return false	`O(n)` time, `O(1)` space

Example: Jump Game I - Can Reach End

function canJump(nums) {
  let maxReach = 0;
  
  for (let i = 0; i < nums.length; i++) {
    // If current position is beyond max reach, can't proceed
    if (i > maxReach) return false;
    
    // Update max reachable position
    maxReach = Math.max(maxReach, i + nums[i]);
    
    // Early exit if can reach end
    if (maxReach >= nums.length - 1) return true;
  }
  
  return true;
}

console.log(canJump([2,3,1,1,4])); // true
console.log(canJump([3,2,1,0,4])); // false

Example: Jump Game II - Minimum Jumps

function minJumps(nums) {
  if (nums.length <= 1) return 0;
  
  let jumps = 0;
  let currentEnd = 0;    // End of current jump range
  let farthest = 0;      // Farthest we can reach
  
  for (let i = 0; i < nums.length - 1; i++) {
    // Update farthest reachable position
    farthest = Math.max(farthest, i + nums[i]);
    
    // When we reach end of current range, must jump
    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;
      
      // Early exit if can reach end
      if (currentEnd >= nums.length - 1) break;
    }
  }
  
  return jumps;
}

// Example: [2,3,1,1,4]
// i=0: farthest=2, jump to range [1,2], jumps=1
// i=1: farthest=4, i=2: reach end of range, jump to range [3,4], jumps=2
console.log(minJumps([2,3,1,1,4])); // 2

3. Gas Station Problem (Circular Array)

Concept	Description	Complexity
Problem	Find starting gas station to complete circular route, given gas[] and cost[] arrays	`O(n)` time
Greedy Insight	If total gas ≥ total cost, solution exists. Start from position where running tank never goes negative	One pass solution
Key Observation	If we can't reach station j from i, then any station between i and j also can't reach j	Skip entire segment

Example: Gas Station Circuit

function canCompleteCircuit(gas, cost) {
  let totalGas = 0, totalCost = 0;
  let tank = 0, start = 0;
  
  for (let i = 0; i < gas.length; i++) {
    totalGas += gas[i];
    totalCost += cost[i];
    tank += gas[i] - cost[i];
    
    // If tank goes negative, can't start from 'start'
    // Try next position as new starting point
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }
  
  // If total gas < total cost, no solution
  return totalGas >= totalCost ? start : -1;
}

const gas = [1,2,3,4,5];
const cost = [3,4,5,1,2];
console.log(canCompleteCircuit(gas, cost)); // 3
// Starting at index 3: tank=4-1=3, then 3+5-2=6, then 6+1-3=4...

Note: The key greedy choice is: if we fail at position j starting from i, we skip all positions between i and j as potential starts, because they have even less fuel accumulated than position i.

4. Interval Scheduling Maximization

Problem Type	Strategy	Sorting Key
Max Non-overlapping	Select maximum count of intervals	Sort by end time (earliest finish)
Min Removal	Remove minimum intervals to make non-overlapping	Sort by end time, count overlaps to remove
Min Meeting Rooms	Minimum rooms needed for all meetings	Sort starts and ends separately, sweep line
Merge Intervals	Merge all overlapping intervals	Sort by start time, merge consecutive overlaps

Example: Minimum Interval Removals

function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;
  
  // Sort by end time
  intervals.sort((a, b) => a[1] - b[1]);
  
  let removals = 0;
  let lastEnd = intervals[0][1];
  
  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    
    if (start < lastEnd) {
      // Overlapping - remove current interval
      removals++;
      // Keep the one with earlier end (already sorted)
    } else {
      // Non-overlapping - update end
      lastEnd = end;
    }
  }
  
  return removals;
}

console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 1
// Remove [1,3] to make all non-overlapping

Example: Minimum Meeting Rooms

function minMeetingRooms(intervals) {
  if (intervals.length === 0) return 0;
  
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
  
  let rooms = 0, endPtr = 0;
  
  for (let i = 0; i < starts.length; i++) {
    // If meeting starts before earliest ending, need new room
    if (starts[i] < ends[endPtr]) {
      rooms++;
    } else {
      // A room becomes available
      endPtr++;
    }
  }
  
  return rooms;
}

console.log(minMeetingRooms([[0,30],[5,10],[15,20]])); // 2

5. Job Sequencing with Deadlines

Concept	Description	Approach
Problem	Given jobs with deadlines and profits, maximize profit by scheduling one job per unit time	Greedy selection
Strategy	Sort jobs by profit (descending), assign each to latest available slot before deadline	`O(n²)` or `O(n log n)`
Data Structure	Use array/set to track occupied time slots, or disjoint set for optimization	Union-Find for O(n log n)

Example: Job Sequencing Problem

function jobSequencing(jobs) {
  // jobs = [[id, deadline, profit], ...]
  // Sort by profit descending
  jobs.sort((a, b) => b[2] - a[2]);
  
  const maxDeadline = Math.max(...jobs.map(j => j[1]));
  const slots = new Array(maxDeadline).fill(null);
  
  let totalProfit = 0;
  const sequence = [];
  
  for (const [id, deadline, profit] of jobs) {
    // Find latest available slot before deadline
    for (let i = Math.min(deadline - 1, maxDeadline - 1); i >= 0; i--) {
      if (slots[i] === null) {
        slots[i] = id;
        totalProfit += profit;
        sequence.push(id);
        break;
      }
    }
  }
  
  return { totalProfit, sequence };
}

const jobs = [
  ['a', 2, 100],
  ['b', 1, 19],
  ['c', 2, 27],
  ['d', 1, 25],
  ['e', 3, 15]
];
console.log(jobSequencing(jobs));
// { totalProfit: 142, sequence: ['a', 'c', 'e'] }

Example: Job Sequencing with Disjoint Set (Optimized)

class DisjointSet {
  constructor(n) {
    this.parent = Array.from({length: n}, (_, i) => i);
  }
  
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  
  union(x, y) {
    this.parent[this.find(x)] = this.find(y);
  }
}

function jobSequencingOptimized(jobs) {
  jobs.sort((a, b) => b[2] - a[2]);
  
  const maxDeadline = Math.max(...jobs.map(j => j[1]));
  const ds = new DisjointSet(maxDeadline + 1);
  
  let totalProfit = 0;
  
  for (const [id, deadline, profit] of jobs) {
    // Find latest available slot
    const slot = ds.find(Math.min(deadline, maxDeadline));
    
    if (slot > 0) {
      ds.union(slot, slot - 1); // Mark as occupied, point to previous
      totalProfit += profit;
    }
  }
  
  return totalProfit;
}

console.log(jobSequencingOptimized(jobs)); // 142

6. Greedy Choice Property Proof

Property	Description	Verification
Greedy Choice	Locally optimal choice leads to globally optimal solution	Proof by exchange argument
Optimal Substructure	Optimal solution contains optimal solutions to subproblems	Required for correctness
Matroid Structure	Problem exhibits matroid properties (hereditary, exchange)	Theoretical foundation
No Backtracking	Once a choice is made, it's never reconsidered	Key difference from DP

Example: Proving Greedy Choice - Fractional Knapsack

// Greedy works for fractional knapsack (not 0/1)
function fractionalKnapsack(items, capacity) {
  // items = [[value, weight], ...]
  // Sort by value-to-weight ratio descending
  items.sort((a, b) => (b[0]/b[1]) - (a[0]/a[1]));
  
  let totalValue = 0;
  let remainingCapacity = capacity;
  
  for (const [value, weight] of items) {
    if (remainingCapacity === 0) break;
    
    // Take as much as possible
    const taken = Math.min(remainingCapacity, weight);
    totalValue += (value / weight) * taken;
    remainingCapacity -= taken;
  }
  
  return totalValue;
}

const items = [[60, 10], [100, 20], [120, 30]];
console.log(fractionalKnapsack(items, 50)); // 240
// Take all of item 2 (ratio=6), all of item 1 (ratio=5), 
// and 2/3 of item 3 (ratio=4) = 100 + 60 + 80 = 240

When Greedy Works

Activity Selection: Sort by end time, select earliest finish
Huffman Coding: Merge two smallest frequencies repeatedly
Dijkstra's Algorithm: Always pick nearest unvisited node
Prim's/Kruskal's MST: Add minimum weight edge that doesn't create cycle
Fractional Knapsack: Sort by value/weight ratio
Coin Change (canonical): Use largest denomination first

Warning: When Greedy Fails

0/1 Knapsack: Need DP, greedy gives wrong answer
Longest Path: NP-hard, greedy doesn't work
Non-canonical Coin Systems: e.g., {1,3,4}, greedy fails for 6
Traveling Salesman: Greedy gives approximation, not optimal

Example: Huffman Coding (Greedy Correctness)

class MinHeap {
  constructor() { this.heap = []; }
  
  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }
  
  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }
  
  bubbleUp(i) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.heap[p].freq <= this.heap[i].freq) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }
  
  bubbleDown(i) {
    while (true) {
      let min = i;
      const left = 2 * i + 1, right = 2 * i + 2;
      if (left < this.heap.length && this.heap[left].freq < this.heap[min].freq) min = left;
      if (right < this.heap.length && this.heap[right].freq < this.heap[min].freq) min = right;
      if (min === i) break;
      [this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
      i = min;
    }
  }
  
  size() { return this.heap.length; }
}

function huffmanCoding(freqMap) {
  const heap = new MinHeap();
  
  // Create leaf nodes
  for (const [char, freq] of Object.entries(freqMap)) {
    heap.push({ char, freq, left: null, right: null });
  }
  
  // Build tree by merging two smallest
  while (heap.size() > 1) {
    const left = heap.pop();
    const right = heap.pop();
    
    heap.push({
      char: null,
      freq: left.freq + right.freq,
      left,
      right
    });
  }
  
  // Generate codes
  const codes = {};
  function traverse(node, code = '') {
    if (node.char) {
      codes[node.char] = code || '0';
      return;
    }
    if (node.left) traverse(node.left, code + '0');
    if (node.right) traverse(node.right, code + '1');
  }
  
  traverse(heap.pop());
  return codes;
}

const freq = { 'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45 };
console.log(huffmanCoding(freq));
// { f: '0', c: '100', d: '101', a: '1100', b: '1101', e: '111' }

Note: To prove greedy correctness, use exchange argument: Assume optimal solution differs from greedy choice. Show you can exchange optimal's choice with greedy's without making solution worse. Repeat until greedy solution is reached, proving it's optimal.

Summary: Greedy Algorithm Pattern

Core Principle: Make locally optimal choice at each step, never backtrack
Activity Selection: Sort by end time, select earliest finish - maximizes remaining time
Jump Game: Track maximum reachable position; for min jumps, use BFS-like levels
Gas Station: If total gas ≥ cost, solution exists; start where tank never goes negative
Interval Scheduling: Various strategies depending on goal (max count, min rooms, min removals)
Job Sequencing: Sort by profit, assign to latest available slot before deadline
Verification: Prove greedy choice property and optimal substructure; use exchange argument
Key Insight: Greedy works when local optimum leads to global optimum - not all problems have this property

Related Cheat Sheets

Algorithm Patterns