Greedy Algorithm Explained With Simple Examples

// Given intervals, find max number of non-overlapping activities
function activitySelection(intervals) {
  // Sort by end time (greedy choice: finish earliest first)
  intervals.sort((a, b) => a[1] - b[1]);

  let count = 1;
  let lastEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= lastEnd) { // starts after last ends
      count++;
      lastEnd = intervals[i][1];
    }
  }

  return count;
}

// Walkthrough:
// Intervals sorted by end: [[1,3],[2,4],[3,5],[0,6],[5,7],[3,9],[5,9],[6,10],[8,11],[8,12],[2,14],[12,16]]
// Take [1,3]: lastEnd=3, count=1
// Skip [2,4]: starts at 2 < lastEnd=3
// Take [3,5]: starts at 3 >= lastEnd=3, count=2, lastEnd=5
// Take [5,7]: starts at 5 >= lastEnd=5, count=3, lastEnd=7
// Take [8,11]: starts at 8 >= lastEnd=7, count=4, lastEnd=11
// Take [12,16]: starts at 12 >= lastEnd=11, count=5

activitySelection([[1,3],[2,4],[3,5],[0,6],[5,7],[3,9],[5,9],[6,10],[8,11],[8,12],[2,14],[12,16]]);
// → 5

// Greedy: track the furthest reachable index at each position
function canJump(nums) {
  let maxReach = 0;

  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false; // stuck — can't reach position i
    maxReach = Math.max(maxReach, i + nums[i]); // extend reach
    if (maxReach >= nums.length - 1) return true; // reached end
  }

  return true;
}

canJump([2,3,1,1,4]); // → true  (0→1→4 or 0→2→3→4)
canJump([3,2,1,0,4]); // → false (always gets stuck at index 3, jump=0)

// Jump Game II — Minimum Jumps (Greedy Level BFS)
function jump(nums) {
  let jumps = 0;
  let currentEnd = 0;  // furthest position reachable with 'jumps' jumps
  let farthest = 0;    // furthest position reachable with 'jumps+1' jumps

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currentEnd) { // used up all positions at current jump count
      jumps++;
      currentEnd = farthest;
    }
  }

  return jumps;
}

jump([2,3,1,1,4]); // → 2 (0→1→4)
jump([2,3,0,1,4]); // → 2 (0→1→4)

// Each balloon is an interval [start, end]. One arrow shot at x bursts all balloons where start≤x≤end.
// Find minimum arrows needed to burst all balloons.
function findMinArrowShots(points) {
  points.sort((a, b) => a[1] - b[1]); // sort by end position

  let arrows = 1;
  let arrowPos = points[0][1]; // shoot first arrow at end of first balloon

  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > arrowPos) { // this balloon starts AFTER current arrow position
      arrows++;                     // need a new arrow
      arrowPos = points[i][1];      // shoot it at this balloon's end
    }
    // else: current arrow already bursts this balloon too (it overlaps)
  }

  return arrows;
}

// Walkthrough: [[10,16],[2,8],[1,6],[7,12]]
// Sorted by end: [[1,6],[2,8],[7,12],[10,16]]
// Arrow 1 at x=6: bursts [1,6] and [2,8] (both contain 6)
// [7,12]: starts at 7 > 6 → Arrow 2 at x=12: bursts [7,12] and [10,16]
// Result: 2 arrows

findMinArrowShots([[10,16],[2,8],[1,6],[7,12]]); // → 2
findMinArrowShots([[1,2],[3,4],[5,6],[7,8]]);    // → 4 (no overlaps)

// n gas stations in a circle. gas[i] = gas at station i, cost[i] = cost to reach station i+1.
// Find starting station for a full circuit, or return -1.
function canCompleteCircuit(gas, cost) {
  let totalGas = 0;     // total surplus across all stations
  let currentGas = 0;   // current surplus from the candidate start
  let start = 0;        // candidate starting station

  for (let i = 0; i < gas.length; i++) {
    const surplus = gas[i] - cost[i];
    totalGas += surplus;
    currentGas += surplus;

    // If we can't reach station i+1 from current 'start', reset
    if (currentGas < 0) {
      start = i + 1;    // try starting from the next station
      currentGas = 0;   // reset running surplus
    }
  }

  // If total gas < total cost, no solution exists
  return totalGas >= 0 ? start : -1;
}

// Key insight: if total gas >= total cost, a solution always exists.
// The greedy: if we run out of gas at station k, no station between
// start and k can be the starting point (they'd run out even sooner).

canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2]); // → 3
canCompleteCircuit([2,3,4], [3,4,3]);          // → -1