Greedy in practice

Implement interval scheduling maximisation and the jump game — two clean greedy algorithms that demonstrate the pattern.

Two problems where the greedy insight is clear once named. Both are O(n) or O(n log n) and far simpler than their DP alternatives.

Two greedy implementations

Python — editable, runs in your browser

# ── 1. Interval scheduling maximisation ──────────────────────────────────────
# Given a list of [start, end] intervals, return the maximum number of
# non-overlapping intervals you can select.
#
# Greedy: sort by end time. Always take the earliest-ending interval that
# doesn't overlap the last selected one.

def max_non_overlapping(intervals):
  if not intervals:
      return 0
  intervals.sort(key=lambda x: x[1])
  count = 0
  last_end = float("-inf")
  for start, end in intervals:
      if start >= last_end:
          count += 1
          last_end = end
  return count

# ── 2. Jump game ──────────────────────────────────────────────────────────────
# Given an array where nums[i] is the max jump length from position i,
# return True if you can reach the last index from position 0.
#
# Greedy: track the furthest index reachable so far. If the current position
# ever exceeds that, you are stuck.

def can_jump(nums):
  max_reach = 0
  for i, jump in enumerate(nums):
      if i > max_reach:
          return False          # can't get here — stuck
      if i + jump > max_reach:
          max_reach = i + jump
  return True

# ── Demo ──────────────────────────────────────────────────────────────────────
print("Interval scheduling")
print(max_non_overlapping([[1,3],[2,4],[3,5],[0,6]]))    # 2
print(max_non_overlapping([[1,2],[2,3],[3,4],[1,3]]))    # 3
print(max_non_overlapping([[1,4],[4,5]]))                # 2  (touching, not overlapping)

print()
print("Jump game")
print(can_jump([2, 3, 1, 1, 4]))   # True
print(can_jump([3, 2, 1, 0, 4]))   # False
print(can_jump([0]))               # True  (already at last index)
print(can_jump([1, 0, 1, 0]))      # False

Why these are greedy

Interval scheduling. Sorting by end time and always taking the earliest available interval is optimal — proved by the exchange argument: any solution that skips the earliest-finishing interval can replace its first selected interval with the earlier-finishing one without reducing the count.

Jump game. Tracking max_reach is the right "local" choice because it captures everything reachable without committing to any specific path. At each position i, you extend max_reach by as much as nums[i] allows. If i exceeds max_reach, no sequence of jumps could have reached position i — return False immediately.

Interval scheduling counts the number of intervals; a related problem asks for the minimum number of intervals to remove so that none overlap. The answer is total - max_non_overlapping. This duality comes up often.

Where to go next

Next: divide and conquer — splitting problems into independent sub-problems, solving each recursively, and combining results. Merge sort, binary search, and quickselect are all divide-and-conquer algorithms.

Finished reading? Mark it complete to track your progress.

Two greedy implementations

Why these are greedy

Where to go next

On this page