Greedy Algorithms

Greedy Algorithms

Problem Scenario / Typical Use Case

Imagine you are managing a set of tasks with deadlines and profits, and you want to maximize total profit by completing tasks on time.

Checking all possible task sequences is infeasible as the number of tasks grows. The Greedy Algorithm pattern provides a local-optimal approach, selecting the “best choice” at each step with the hope of reaching a global optimum.

Basic Idea

Greedy algorithms make locally optimal choices at each step with the aim of achieving a global optimum.

Typical operations include:

• Selecting tasks or intervals to maximize/minimize a value.
• Making change with minimal coins.
• Activity or job scheduling.
• Huffman encoding and other compression techniques.

Advantages

• Efficiency: Usually runs in linearithmic or linear time, depending on sorting.
• Simplicity: Easy to implement and reason about.
• Versatility: Works for optimization problems with clear local decision rules.

Limitations / Considerations

• Greedy is not universally optimal; it works only when the problem satisfies the greedy-choice property and optimal substructure.
• Requires careful analysis to ensure local decisions lead to global optimality.
• May fail for some problems where a global perspective is needed (e.g., some DP problems).

Practical Examples / Thought Triggers

1. Activity Selection Problem: Choose the maximum number of non-overlapping activities.
2. Interval Scheduling: Select intervals to maximize total weight or profit.
3. Coin Change Problem: Use the largest denominations first (works optimally with canonical coin systems).

Thought Triggers:

• Does the problem guarantee that greedy choices lead to global optimality?
• Can sorting the input simplify the greedy selection?
• Should this be combined with other patterns like Merge Intervals or Sorting-Based Patterns?

Implementation Example

Here’s a Python example for maximizing activities that don’t overlap:

def max_activities(activities):
    # Sort by end time
    activities.sort(key=lambda x: x[1])
    count = 0
    last_end = float('-inf')

    for start, end in activities:
        if start >= last_end:
            count += 1
            last_end = end

    return count

# Example usage
tasks = [(1, 3), (2, 5), (4, 6), (6, 8)]
print(max_activities(tasks))
# Output: 3 (activities: [1,3], [4,6], [6,8])

This demonstrates how greedy selection after sorting can efficiently maximize non-overlapping activities.

Related Articles

• Sorting-Based Patterns: Sorting is often necessary before greedy selection.
• Merge Intervals / Overlapping Intervals: Greedy decisions can be applied to interval-based problems.
• Two Pointers: Can complement greedy approaches in linear scans of sorted data.