Greedy algorithms

Greedy is not “take the largest” or “sort and hope.” It is a proof that one locally chosen action can be part of an optimal solution.

Proof chooser

flowchart TD
  accTitle: Deciding whether a greedy choice is justified
  accDescr: Try an exchange argument when an optimal first choice can be swapped with the greedy choice, a stay-ahead proof when prefixes can be compared, and a cut property for spanning structures. If no proof survives a small counterexample, use dynamic programming or search.
  A["Propose a local choice"] --> B{"Can any optimum swap its first<br/>different choice with yours?"}
  B -->|yes| C["Exchange argument"]
  B -->|no| D{"Can every greedy prefix be<br/>shown at least as good?"}
  D -->|yes| E["Stay-ahead proof"]
  D -->|no| F{"Does a cut certify the<br/>cheapest safe connector?"}
  F -->|yes| G["Cut-property greedy"]
  F -->|no| H["Seek DP, flow, or search"]

Interval scheduling

For the largest set of non-overlapping half-open intervals, choose the compatible interval that ends earliest. Any optimum's first interval can be replaced by this one without reducing space for later choices.

PythonC++17C++11

def max_non_overlapping_intervals(intervals: Iterable[tuple[int, int]]) -> int:
    """Return the largest compatible set of half-open intervals."""
    ordered = sorted(intervals, key=lambda interval: interval[1])
    selected = 0
    previous_end: int | None = None
    for start, end in ordered:
        if start > end:
            raise ValueError("interval start must not exceed end")
        if previous_end is None or start >= previous_end:
            # The earliest finishing compatible interval leaves most room.
            selected += 1
            previous_end = end
    return selected

inline int max_non_overlapping_intervals(
    std::vector<std::pair<int, int>> intervals) {
  for (const auto& interval : intervals) {
    if (interval.first > interval.second) {
      throw std::invalid_argument("interval start must not exceed end");
    }
  }
  std::sort(intervals.begin(), intervals.end(),
            [](const std::pair<int, int>& left,
               const std::pair<int, int>& right) {
              return left.second < right.second;
            });
  int selected = 0;
  int previous_end = 0;
  bool has_previous = false;
  for (const auto& interval : intervals) {
    if (!has_previous || interval.first >= previous_end) {
      // The earliest finishing compatible interval leaves most room.
      ++selected;
      previous_end = interval.second;
      has_previous = true;
    }
  }
  return selected;
}

inline int max_non_overlapping_intervals(
    std::vector<std::pair<int, int>> intervals) {
  for (const auto& interval : intervals) {
    if (interval.first > interval.second) {
      throw std::invalid_argument("interval start must not exceed end");
    }
  }
  std::sort(intervals.begin(), intervals.end(),
            [](const std::pair<int, int>& left,
               const std::pair<int, int>& right) {
              return left.second < right.second;
            });
  int selected = 0;
  int previous_end = 0;
  bool has_previous = false;
  for (const auto& interval : intervals) {
    if (!has_previous || interval.first >= previous_end) {
      // The earliest finishing compatible interval leaves most room.
      ++selected;
      previous_end = interval.second;
      has_previous = true;
    }
  }
  return selected;
}

Sorting dominates at O(n log n) time; the scan is O(n).

Greedy or DP?

Use greedy when the exchange keeps every future option at least as good. Use DP when the best next choice depends on remaining capacity, parity, history, or another state dimension. Weighted interval scheduling is the classic warning: earliest finish maximizes count, not total weight.

Practice ladder

1. Assign Cookies — match two sorted frontiers.
2. Non-overlapping Intervals — earliest finish.
3. Jump Game — farthest reachable prefix.
4. Gas Station — discard impossible start prefixes.