Skip to main content

Advanced Greedy

TL;DR​

Advanced greedy combines sorting strategies with priority queues for complex problems. Greedy + Sorting: Different sort orders yield different optimal solutions; choosing right metric is crucial. Examples: sort by deadlines for job sequencing, by ratios for load balancing, by multiple keys for tie-breaking. Priority Queue Greedy: Maintain priority queue to always process most favorable element; task scheduling maintains queue of pending tasks, selecting highest-priority ready task. Greedy Proofs: Use exchange argument (modify non-greedy solution toward greedy), induction (maintain invariant), or contradiction (assume greedy fails). When Greedy Fails: Lack of greedy choice property (e.g., arbitrary coin change), interdependencies between choices (e.g., 0/1 knapsack), problems requiring global optimization (e.g., cliques). Recognize failure cases: counterexamples disprove greedy; DP/backtracking required instead. Advanced greedy succeeds by combining multiple techniques: smart sorting orders, priority queue operations, careful proofs.

Core Concepts​

Greedy Sorting Strategies​

Different sorting orders optimize different objectives:

End-time sorting (earliest finish): Activity selection, interval problems Start-time sorting (earliest start): Resource allocation, timeline construction Value sorting (highest first): Job profit optimization, priority allocation Ratio sorting (value/weight): Knapsack variants, resource efficiency Deadline sorting (earliest deadline): Task scheduling, deadline management Multiple key sorting: Tie-breaking when primary sort yields equal values

Key Insight: Wrong sort order makes greedy fail. Always verify sort matches problem objective.

Priority Queue Integration​

Priority queue maintains elements in order of importance, enabling O(log n) insertion/deletion.

Patterns:

  • Min-heap: Select smallest element (earliest finish, lowest cost)
  • Max-heap: Select largest element (highest profit, maximum value)
  • Custom priority: Define comparison function for problem-specific ordering

Complexity: Building queue O(n), each operation O(log n), total O(n log n) for n operations.

Task Scheduler Patterns​

Advanced task scheduling combines multiple constraints:

State: Current time, running tasks, pending queue, task deadlines Greedy Choice: Among ready tasks, select highest-priority by criteria Constraint Management: Respect deadlines, resource limits, dependencies

Example: Minimize task completion time while respecting deadlines—use earliest deadline first with tie-breaking by task priority.

Recognizing Greedy Failures​

Failure Patterns:

  1. Counterexample exists: Simple test case where greedy fails
  2. Choice interdependencies: Decision affects feasibility of future choices
  3. No clear local optimum: Multiple reasonable criteria compete
  4. Global constraint: Solution requires considering problem holistically

Recovery Options:

  • Switch to DP (optimal substructure without greedy choice)
  • Use backtracking/search (explore multiple paths)
  • Apply approximation (greedy provides good but not optimal solution)

Key Algorithms​

Task Scheduler with Deadlines​

Problem: Minimize lateness (maximum delay from deadline) for scheduled tasks.

State: Current time, completed tasks, remaining tasks, task deadlines

Greedy Choice: Earliest deadline first—always execute ready task with earliest deadline

Why It Works: Exchange argument: if task i has later deadline than task j but i executes before j, swap them and reduce or maintain lateness.

Load Balancing​

Problem: Distribute tasks across machines minimizing maximum load.

State: Current machine loads, tasks remaining

Greedy Choice: Assign next task to least-loaded machine

Why It Works: Greedy distributes load evenly; assigning to least-loaded prevents concentration.

Multiple Sorting Keys​

Problem: Optimize multiple objectives simultaneously.

Strategy:

  1. Identify primary objective
  2. Sort by primary metric
  3. For ties, apply secondary sort
  4. Continue for tertiary sorts as needed

Example: Schedule meetings by start time; for same start, prefer shorter duration; for same duration, prefer higher priority.

Practical Example​

import heapq
from typing import List, Tuple

# Task Scheduler - Minimize Lateness
def task_scheduler_minimize_lateness(tasks):
    """
    tasks: list of (task_id, duration, deadline)
    Returns schedule and maximum lateness
    """
    # Sort by deadline (earliest first)
    sorted_tasks = sorted(tasks, key=lambda x: x[2])

    current_time = 0
    max_lateness = 0
    schedule = []

    for task_id, duration, deadline in sorted_tasks:
        start = current_time
        end = current_time + duration
        lateness = max(0, end - deadline)
        max_lateness = max(max_lateness, lateness)

        schedule.append((task_id, start, end, lateness))
        current_time = end

    return schedule, max_lateness

# Load Balancing - Minimize Max Load
def load_balancing(tasks, num_machines):
    """
    tasks: list of task durations
    Returns assignment of tasks to machines and max load
    """
    # Min-heap: (current_load, machine_id)
    machines = [(0, i) for i in range(num_machines)]
    heapq.heapify(machines)

    assignment = {i: [] for i in range(num_machines)}

    for task_duration in tasks:
        load, machine_id = heapq.heappop(machines)
        assignment[machine_id].append(task_duration)
        new_load = load + task_duration
        heapq.heappush(machines, (new_load, machine_id))

    max_load = max(load for load, _ in machines)
    return assignment, max_load

# Multiple Sort Keys
def meeting_scheduler(meetings):
    """
    meetings: list of (meeting_id, start, duration, priority)
    Returns schedule sorted by multiple criteria
    """
    # Primary: start time, Secondary: duration, Tertiary: priority (descending)
    sorted_meetings = sorted(meetings,
                           key=lambda x: (x[1], x[2], -x[3]))

    return sorted_meetings

# Priority Queue Greedy - Task Selection
def task_selection_with_priority(tasks):
    """
    tasks: list of (task_id, duration, priority, deadline)
    Returns ordered task execution
    """
    # Max-heap for priority (negate for Python's min-heap)
    heap = [(-task[2], task) for task in tasks]
    heapq.heapify(heap)

    execution_order = []
    current_time = 0

    while heap:
        _, (task_id, duration, priority, deadline) = heapq.heappop(heap)

        # Check if task can complete before deadline
        if current_time + duration <= deadline:
            execution_order.append((task_id, current_time, current_time + duration))
            current_time += duration
        # else: skip task (deadline impossible)

    return execution_order

# Greedy Failure Example - Coin Change
def coin_change_greedy_fails():
    """
    Demonstrates where greedy fails for coin change
    """
    coins = [1, 3, 4]
    amount = 6

    # Greedy approach (wrong for some cases)
    greedy_count = 0
    remaining = amount
    for coin in sorted(coins, reverse=True):
        greedy_count += remaining // coin
        remaining %= coin

    # Optimal: use two 3-coins = 2 coins
    # Greedy might use 4+1+1 = 3 coins (greedy picks 4 first)

    optimal = 2
    return greedy_count, optimal

# Tests
tasks = [('A', 3, 5), ('B', 2, 3), ('C', 4, 6)]
schedule, lateness = task_scheduler_minimize_lateness(tasks)
print(f"Schedule: {schedule}, Max Lateness: {lateness}")

task_durations = [5, 3, 8, 2, 7]
assignment, max_load = load_balancing(task_durations, 2)
print(f"Assignment: {assignment}, Max Load: {max_load}")

meetings = [('m1', 10, 30, 2), ('m2', 10, 20, 1), ('m3', 15, 15, 3)]
print(meeting_scheduler(meetings))

tasks_pq = [('t1', 2, 5, 10), ('t2', 3, 4, 8), ('t3', 1, 3, 5)]
print(task_selection_with_priority(tasks_pq))

greedy_result, optimal_result = coin_change_greedy_fails()
print(f"Greedy: {greedy_result}, Optimal: {optimal_result}")

Common Pitfalls​

warning

Wrong sorting criterion: Sort order directly impacts greedy optimality. Verify sort matches problem objective, not just intuition.

Ignoring priority queue overhead: O(log n) per operation adds up; ensure priority queue benefits outweigh overhead for problem size.

Insufficient proof of correctness: Advanced greedy requires rigorous proof. Exchange argument or induction insufficient? Likely wrong.

Missing edge cases in deadline/constraint handling: Off-by-one errors in deadline checks or constraint satisfaction cause incorrect solutions.

Not recognizing failure patterns: Spend too long debugging greedy that won't work. Recognize failure quickly, pivot to DP or search.

Greedy works on small test cases: Greedy might pass examples by luck. Prove correctness abstractly, not just empirically.

Self-Check​

  1. Why does earliest deadline first minimize maximum lateness? Can you prove with exchange argument?
  2. In load balancing, why does assigning to least-loaded machine work? What property does it maintain?
  3. When would multiple sort keys help? Give an example beyond meeting scheduling.

One Takeaway​

info

Advanced greedy succeeds by combining multiple techniques: choosing right sorting order, leveraging priority queues, and proving correctness rigorously. The breakthrough comes from recognizing when greedy applies and engineering the right solution structure. Master sorting strategies, priority queue operations, and proof techniques, and you'll handle complex optimization problems elegantly. Always validate greedy applicability; if counterexample exists, switch approaches immediately rather than persisting with failing greedy.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson Education.