Welcome to Greedy CodeSnap

Greedy algorithms build up a solution piece by piece, always choosing the option that offers the most obvious and immediate benefit at the current step, hoping to find a global optimum. While not always yielding the optimal solution for all problems, they are effective for many optimization tasks like scheduling (Activity Selection, Minimum Platforms), resource allocation (Assign Cookies, Fractional Knapsack), pathfinding (Jump Game), interval problems (Merge Intervals, Non-overlapping Intervals), and data compression (Huffman Encoding). The key is identifying the correct greedy choice property that leads to the optimal result.

Table of Contents

• Assign Cookies

  Assume you are an awesome parent wanting to give cookies to your children. Each child `i` has a greed factor `g[i]`, and each cookie `j` has a size `s[j]`. You can assign cookie `j` to child `i` if `s[j] >= g[i]`. Maximize the number of content children. A greedy approach involves sorting both arrays and satisfying the least greedy child first with the smallest suitable cookie.

• Gas Station

  There are N gas stations along a circular route. You are given the amount of gas at station `i` (`gas[i]`) and the cost to travel from station `i` to `i+1` (`cost[i]`). Find the starting gas station's index if you can travel around the circuit once, otherwise return -1. A greedy approach checks if a solution is possible (total gas >= total cost) and finds the start by tracking the current tank level.

• Jump Game

  Given an array `nums` where `nums[i]` is the maximum jump length from index `i`, determine if you can reach the last index starting from the first index. The greedy strategy involves tracking the farthest reachable index at each step.

• Minimum Number of Arrows to Burst Balloons

  Given points representing balloon diameters `[x_start, x_end]`, find the minimum arrows shot vertically to burst all balloons. An arrow at `x` bursts balloons where `x_start <= x <= x_end`. Greedy approach: Sort by end points, shoot at the end of the first balloon, and skip already burst balloons.

• Non-overlapping Intervals

  Given a collection of intervals `[start, end]`, find the minimum number of intervals to remove so that the remaining intervals do not overlap. Greedy approach (related to Activity Selection): Sort by end times, then count the maximum number of non-overlapping intervals you can keep.

• Merge Intervals

  Given an array of intervals `intervals[i] = [start_i, end_i]`, merge all overlapping intervals and return an array of the non-overlapping intervals covering all original intervals. Greedy approach: Sort by start time, then iterate and merge if overlap exists.

• Lemonade Change

  At a lemonade stand, customers order one $5 lemonade and pay with $5, $10, or $20 bills. Start with no change. Return true if you can provide correct change to every customer. Greedy approach: Always try to use larger denomination bills ($10 before $5) when giving change for a $20.

• Can Place Flowers

  Given a flowerbed array `flowerbed` (0=empty, 1=planted) and integer `n`, check if `n` new flowers can be planted without violating the no-adjacent-flowers rule. Greedy approach: Iterate through the bed, planting a flower whenever an empty spot has empty neighbors.

• Minimum Platforms (Train Schedule)

  Given arrival and departure times of trains at a station, find the minimum number of platforms required so that no train has to wait. Greedy approach: Sort arrival and departure times independently. Scan through time, incrementing platform count for arrivals and decrementing for departures, tracking the maximum count needed.

• Activity Selection

  Given N activities with their start and finish times, select the maximum number of activities that can be performed by a single person, assuming only one activity can be worked on at a time. Greedy approach: Sort activities by finish time. Select the first activity, then iteratively select the next compatible activity (start time >= finish time of last selected).

• Job Sequencing Problem

  Given a set of jobs, each with a deadline and profit, schedule the jobs (each takes 1 unit time) to maximize total profit. Only one job can be scheduled at a time. Greedy approach: Sort jobs by decreasing profit. For each job, schedule it in the latest possible time slot less than or equal to its deadline.

• Fractional Knapsack

  Given weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value. You can take fractions of items. Greedy approach: Calculate value-to-weight ratio for each item. Sort items by decreasing ratio. Fill the knapsack greedily with items/fractions of items having the highest ratios.

• Huffman Encoding

  Generate Huffman codes, which are optimal prefix codes used for lossless data compression. Given characters and their frequencies, build a Huffman tree using a min-priority queue. The greedy strategy involves repeatedly merging the two nodes with the lowest frequencies.

• Reorganize String

  Given a string `s`, rearrange its characters so that no two adjacent characters are the same. Return any valid rearrangement, or "" if impossible. Greedy approach: Use a max-heap or frequency counts. At each step, append the most frequent character different from the last appended character.

• Candy Distribution

  Children are lined up with ratings. Distribute candies such that each child gets at least one, and children with higher ratings get more candies than their immediate neighbors. Find the minimum total candies required. Greedy approach: Use two passes (left-to-right and right-to-left) to satisfy neighbor conditions.