Coding Patterns
Greedy Algorithms
Code Templates

Code Templates

Now that you understand the greedy algorithm concept, let’s dive into practical implementations. This page provides standardized, memorizable code “blueprints” that can be adapted to most greedy problems.

The “Main” Template: Activity Selection

This is the most fundamental greedy pattern - selecting the maximum number of non-overlapping intervals. It demonstrates the core greedy principle of always choosing the locally optimal option.

Description: Given a set of activities with start and end times, select the maximum number of activities that don’t overlap. This template directly solves the classic Activity Selection problem and forms the foundation for many other interval-based greedy problems.

/**
 * Activity Selection - Greedy Algorithm Template
 * @param {Array} activities - Array of [start, end] pairs
 * @returns {Array} Selected activities
 */
function activitySelection(activities) {
    // Sort by end time (greedy choice: earliest finish)
    activities.sort((a, b) => a[1] - b[1]);

    const selected = [];
    let lastEnd = -Infinity;

    for (const [start, end] of activities) {
        // Greedy condition: no overlap with last selected
        if (start >= lastEnd) {
            selected.push([start, end]);
            lastEnd = end;
        }
    }

    return selected;
}

// Usage example
const activities = [[1, 4], [3, 5], [0, 6], [5, 7], [8, 9], [5, 9]];
console.log(activitySelection(activities)); // [[1,4], [5,7], [8,9]]

def activity_selection(activities):
    """
    Activity Selection - Greedy Algorithm Template
    Args:
        activities: List of [start, end] pairs
    Returns:
        List of selected activities
    """
    # Sort by end time (greedy choice: earliest finish)
    activities.sort(key=lambda x: x[1])

    selected = []
    last_end = float('-inf')

    for start, end in activities:
        # Greedy condition: no overlap with last selected
        if start >= last_end:
            selected.append([start, end])
            last_end = end

    return selected

# Usage example
activities = [[1, 4], [3, 5], [0, 6], [5, 7], [8, 9], [5, 9]]
print(activity_selection(activities))  # [[1,4], [5,7], [8,9]]
import java.util.*;

public class ActivitySelection {
    /**
     * Activity Selection - Greedy Algorithm Template
     * @param activities 2D array where each row is [start, end]
     * @return List of selected activities
     */
    public static List<int[]> activitySelection(int[][] activities) {
        // Sort by end time (greedy choice: earliest finish)
        Arrays.sort(activities, (a, b) -> Integer.compare(a[1], b[1]));

        List<int[]> selected = new ArrayList<>();
        int lastEnd = Integer.MIN_VALUE;

        for (int[] activity : activities) {
            int start = activity[0];
            int end = activity[1];

            // Greedy condition: no overlap with last selected
            if (start >= lastEnd) {
                selected.add(activity);
                lastEnd = end;
            }
        }

        return selected;
    }

    // Usage example
    public static void main(String[] args) {
        int[][] activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
        List<int[]> result = activitySelection(activities);
        for (int[] act : result) {
            System.out.println(Arrays.toString(act));
        }
        // Output: [1, 4], [5, 7], [8, 9]
    }
}
#include <vector>
#include <algorithm>
#include <iostream>

class ActivitySelection {
public:
    /**
     * Activity Selection - Greedy Algorithm Template
     * @param activities Vector of pairs where each pair is {start, end}
     * @return Vector of selected activities
     */
    static std::vector<std::pair<int, int>> activitySelection(
        std::vector<std::pair<int, int>>& activities) {

        // Sort by end time (greedy choice: earliest finish)
        std::sort(activities.begin(), activities.end(),
                 [](const auto& a, const auto& b) {
                     return a.second < b.second;
                 });

        std::vector<std::pair<int, int>> selected;
        int lastEnd = INT_MIN;

        for (const auto& activity : activities) {
            int start = activity.first;
            int end = activity.second;

            // Greedy condition: no overlap with last selected
            if (start >= lastEnd) {
                selected.push_back(activity);
                lastEnd = end;
            }
        }

        return selected;
    }
};

// Usage example
int main() {
    std::vector<std::pair<int, int>> activities = {
        {1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}
    };

    auto result = ActivitySelection::activitySelection(activities);
    for (const auto& act : result) {
        std::cout << "[" << act.first << ", " << act.second << "] ";
    }
    // Output: [1, 4] [5, 7] [8, 9]
    return 0;
}
package main

import (
	"fmt"
	"sort"
)

// Activity represents a start-end pair
type Activity struct {
	Start, End int
}

/**
 * Activity Selection - Greedy Algorithm Template
 * @param activities slice of Activity structs
 * @return slice of selected activities
 */
func activitySelection(activities []Activity) []Activity {
	// Sort by end time (greedy choice: earliest finish)
	sort.Slice(activities, func(i, j int) bool {
		return activities[i].End < activities[j].End
	})

	var selected []Activity
	lastEnd := -1 << 31 // MinInt32

	for _, activity := range activities {
		// Greedy condition: no overlap with last selected
		if activity.Start >= lastEnd {
			selected = append(selected, activity)
			lastEnd = activity.End
		}
	}

	return selected
}

// Usage example
func main() {
	activities := []Activity{
		{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9},
	}

	result := activitySelection(activities)
	for _, act := range result {
		fmt.Printf("[%d, %d] ", act.Start, act.End)
	}
	// Output: [1, 4] [5, 7] [8, 9]
}
def activity_selection(activities)
  # Activity Selection - Greedy Algorithm Template
  # @param activities Array of [start, end] pairs
  # @return Array of selected activities

  # Sort by end time (greedy choice: earliest finish)
  activities.sort_by! { |activity| activity[1] }

  selected = []
  last_end = -Float::INFINITY

  activities.each do |start, end|
    # Greedy condition: no overlap with last selected
    if start >= last_end
      selected << [start, end]
      last_end = end
    end
  end

  selected
end

# Usage example
activities = [[1, 4], [3, 5], [0, 6], [5, 7], [8, 9], [5, 9]]
puts activity_selection(activities).inspect
# Output: [[1, 4], [5, 7], [8, 9]]

Code Breakdown

Key Variables

  • activities: Input array of intervals/activities to process
  • lastEnd: Tracks the end time of the last selected activity
  • selected: Stores the final set of chosen activities

Critical Sections

  1. Initialization: Sort by end time to enable greedy selection
  2. Greedy Loop: For each activity, check if it doesn’t overlap with the last selected
  3. Selection: If no overlap, add to selected set and update lastEnd

Visual Algorithm Flow 

  flowchart TD
    A[Start] --> B[Sort by end time]
    B --> C[Initialize lastEnd = -∞]
    C --> D[Iterate through activities]
    D --> E{start >= lastEnd?}
    E -->|Yes| F[Select activity]
    E -->|No| G[Skip activity]
    F --> H[Update lastEnd]
    H --> I{More activities?}
    G --> I
    I -->|Yes| D
    I -->|No| J[Return selected]
    J --> K[End]

Variations

1. Fractional Knapsack 

function fractionalKnapsack(weights, values, capacity) {
    // Create items with value-to-weight ratio
    const items = weights.map((weight, i) => ({
        weight,
        value: values[i],
        ratio: values[i] / weight
    }));

    // Sort by ratio (descending)
    items.sort((a, b) => b.ratio - a.ratio);

    let totalValue = 0;
    let remainingCapacity = capacity;

    for (const item of items) {
        if (remainingCapacity >= item.weight) {
            // Take whole item
            totalValue += item.value;
            remainingCapacity -= item.weight;
        } else {
            // Take fraction of item
            totalValue += item.ratio * remainingCapacity;
            break;
        }
    }

    return totalValue;
}
def fractional_knapsack(weights, values, capacity):
    # Create items with value-to-weight ratio
    items = [(weights[i], values[i], values[i]/weights[i])
             for i in range(len(weights))]

    # Sort by ratio (descending)
    items.sort(key=lambda x: x[2], reverse=True)

    total_value = 0
    remaining_capacity = capacity

    for weight, value, ratio in items:
        if remaining_capacity >= weight:
            # Take whole item
            total_value += value
            remaining_capacity -= weight
        else:
            # Take fraction of item
            total_value += ratio * remaining_capacity
            break

    return total_value
public static double fractionalKnapsack(int[] weights, int[] values, int capacity) {
    // Create items with value-to-weight ratio
    Item[] items = new Item[weights.length];
    for (int i = 0; i < weights.length; i++) {
        items[i] = new Item(weights[i], values[i], (double)values[i]/weights[i]);
    }

    // Sort by ratio (descending)
    Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));

    double totalValue = 0;
    int remainingCapacity = capacity;

    for (Item item : items) {
        if (remainingCapacity >= item.weight) {
            // Take whole item
            totalValue += item.value;
            remainingCapacity -= item.weight;
        } else {
            // Take fraction of item
            totalValue += item.ratio * remainingCapacity;
            break;
        }
    }

    return totalValue;
}

static class Item {
    int weight, value;
    double ratio;
    Item(int weight, int value, double ratio) {
        this.weight = weight; this.value = value; this.ratio = ratio;
    }
}
double fractionalKnapsack(vector<int>& weights, vector<int>& values, int capacity) {
    vector<Item> items;
    for (int i = 0; i < weights.size(); i++) {
        items.push_back({weights[i], values[i], (double)values[i]/weights[i]});
    }

    // Sort by ratio (descending)
    sort(items.begin(), items.end(),
         [](const Item& a, const Item& b) { return a.ratio > b.ratio; });

    double totalValue = 0;
    int remainingCapacity = capacity;

    for (const auto& item : items) {
        if (remainingCapacity >= item.weight) {
            // Take whole item
            totalValue += item.value;
            remainingCapacity -= item.weight;
        } else {
            // Take fraction of item
            totalValue += item.ratio * remainingCapacity;
            break;
        }
    }

    return totalValue;
}

struct Item {
    int weight, value;
    double ratio;
};
func fractionalKnapsack(weights, values []int, capacity int) float64 {
    type item struct {
        weight, value int
        ratio float64
    }

    // Create items with value-to-weight ratio
    items := make([]item, len(weights))
    for i := range weights {
        items[i] = item{
            weight: weights[i],
            value:  values[i],
            ratio:  float64(values[i]) / float64(weights[i]),
        }
    }

    // Sort by ratio (descending)
    sort.Slice(items, func(i, j int) bool {
        return items[i].ratio > items[j].ratio
    })

    var totalValue float64
    remainingCapacity := capacity

    for _, item := range items {
        if remainingCapacity >= item.weight {
            // Take whole item
            totalValue += float64(item.value)
            remainingCapacity -= item.weight
        } else {
            // Take fraction of item
            totalValue += item.ratio * float64(remainingCapacity)
            break
        }
    }

    return totalValue
}
def fractional_knapsack(weights, values, capacity)
  # Create items with value-to-weight ratio
  items = weights.each_with_index.map do |weight, i|
    { weight: weight, value: values[i], ratio: values[i].fdiv(weight) }
  end

  # Sort by ratio (descending)
  items.sort_by! { |item| -item[:ratio] }

  total_value = 0.0
  remaining_capacity = capacity

  items.each do |item|
    if remaining_capacity >= item[:weight]
      # Take whole item
      total_value += item[:value]
      remaining_capacity -= item[:weight]
    else
      # Take fraction of item
      total_value += item[:ratio] * remaining_capacity
      break
    end
  end

  total_value
end

2. Jump Game 

function canJump(nums) {
    let maxReach = 0;

    for (let i = 0; i < nums.length; i++) {
        // Cannot reach current position
        if (i > maxReach) return false;

        // Update maximum reachable position
        maxReach = Math.max(maxReach, i + nums[i]);

        // Can reach end
        if (maxReach >= nums.length - 1) return true;
    }

    return true;
}
def can_jump(nums):
    max_reach = 0

    for i in range(len(nums)):
        # Cannot reach current position
        if i > max_reach:
            return False

        # Update maximum reachable position
        max_reach = max(max_reach, i + nums[i])

        # Can reach end
        if max_reach >= len(nums) - 1:
            return True

    return True
public static boolean canJump(int[] nums) {
    int maxReach = 0;

    for (int i = 0; i < nums.length; i++) {
        // Cannot reach current position
        if (i > maxReach) return false;

        // Update maximum reachable position
        maxReach = Math.max(maxReach, i + nums[i]);

        // Can reach end
        if (maxReach >= nums.length - 1) return true;
    }

    return true;
}
bool canJump(vector<int>& nums) {
    int maxReach = 0;

    for (int i = 0; i < nums.size(); i++) {
        // Cannot reach current position
        if (i > maxReach) return false;

        // Update maximum reachable position
        maxReach = max(maxReach, i + nums[i]);

        // Can reach end
        if (maxReach >= nums.size() - 1) return true;
    }

    return true;
}
func canJump(nums []int) bool {
    maxReach := 0

    for i := 0; i < len(nums); i++ {
        // Cannot reach current position
        if i > maxReach {
            return false
        }

        // Update maximum reachable position
        if i+nums[i] > maxReach {
            maxReach = i + nums[i]
        }

        // Can reach end
        if maxReach >= len(nums)-1 {
            return true
        }
    }

    return true
}
def can_jump(nums)
  max_reach = 0

  nums.each_with_index do |jump, i|
    # Cannot reach current position
    return false if i > max_reach

    # Update maximum reachable position
    max_reach = [max_reach, i + jump].max

    # Can reach end
    return true if max_reach >= nums.length - 1
  end

  true
end

Practice

Now that you have these templates, head to the Practice Problems page to apply these patterns to real coding challenges. Each problem will help you understand when and how to adapt these templates for different scenarios.