{
    "api": "YAML JSON TOON Database",
    "version": "1.0.0",
    "format": "json",
    "dataset": {
        "id": 2804,
        "slug": "greedy-algorithms",
        "title": "Greedy Algorithms",
        "description": "Algorithms that make locally optimal choices at each step.",
        "summary": "Greedy algorithms and the problems they solve: activity selection, Huffman coding, Dijkstra, Kruskal, fractional knapsack and job sequencing, extended with Prim's and Boruvka's spanning-tree algorithms, canonical coin change, optimal merge patterns and greedy set-cover approximation.",
        "use_when": [
            "You need a canonical example of a greedy strategy.",
            "You are checking whether a problem fits the greedy-choice property."
        ],
        "caveats": [
            "Greedy gives optimal answers only for problems with the greedy-choice property; the 0\/1 knapsack and general coin change are counterexamples.",
            "A greedy algorithm can still be a good approximation when it is not optimal, as for set cover."
        ],
        "related": [
            "dynamic-programming-patterns",
            "graph-algorithms",
            "graph-traversal-algorithms",
            "complexity-classes"
        ],
        "entry_count": 11,
        "fields": [
            {
                "section": "data",
                "field": "algorithm",
                "type": "string",
                "example": "Activity Selection"
            },
            {
                "section": "data",
                "field": "use_case",
                "type": "string",
                "example": "Select maximum compatible activities given star\u2026"
            }
        ],
        "category": "Algorithms",
        "category_slug": "algorithms",
        "tags": "algorithms,greedy,optimization",
        "view_count": 45,
        "created_at": 1793403093,
        "updated_at": 1793403093
    },
    "data": [
        {
            "algorithm": "Activity Selection",
            "use_case": "Select maximum compatible activities given start and end times."
        },
        {
            "algorithm": "Huffman Coding",
            "use_case": "Build optimal prefix-free binary encoding for symbols."
        },
        {
            "algorithm": "Dijkstra Shortest Path",
            "use_case": "Find shortest paths from a source in graphs with non-negative weights."
        },
        {
            "algorithm": "Kruskal MST",
            "use_case": "Build minimum spanning tree by adding cheapest edges."
        },
        {
            "algorithm": "Fractional Knapsack",
            "use_case": "Maximize value when items can be broken into fractions."
        },
        {
            "algorithm": "Job Sequencing",
            "use_case": "Schedule jobs with deadlines to maximize profit."
        },
        {
            "algorithm": "Prim's MST",
            "use_case": "Grow a minimum spanning tree by repeatedly adding the cheapest edge that connects a new vertex."
        },
        {
            "algorithm": "Boruvka's MST",
            "use_case": "Build a minimum spanning tree by adding the cheapest outgoing edge of every component in parallel rounds."
        },
        {
            "algorithm": "Coin Change (canonical systems)",
            "use_case": "Make change with the fewest coins using the largest coin first; optimal only for canonical coin systems such as US coins."
        },
        {
            "algorithm": "Optimal Merge Pattern",
            "use_case": "Merge sorted files with minimum total cost by always merging the two smallest."
        },
        {
            "algorithm": "Greedy Set Cover",
            "use_case": "Approximate the smallest collection of sets covering all elements by repeatedly picking the set that covers the most uncovered elements."
        }
    ]
}