Unit 4: Greedy techniques - Subjective Questions

The greedy paradigm is an algorithmic strategy that builds up a solution piece by piece, always choosing the option that offers the most immediate benefit (the locally optimal choice) at each step, with the hope that these local choices lead to a globally optimal solution.

Key Characteristics:

• Greedy Choice Property: A global optimum can be reached by making a locally optimal choice at each step.
• Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.
• No Backtracking: Once a choice is made, it is never reconsidered.

General Steps:

1. Determine the optimal substructure of the problem.
2. Develop a recursive solution.
3. Show that if we make the greedy choice, only one subproblem remains.
4. Prove that the greedy choice is always safe.
5. Convert the recursive algorithm into an iterative one.

Advantages: Simple to implement, efficient (often ).

Limitation: Does not always produce the globally optimal solution (e.g., the general Knapsack problem).

Locally Optimal Choice: The best decision made at a particular step, considering only the current state without regard to future consequences.

Globally Optimal Choice: The overall best solution to the entire problem across all steps.

Example (Coin Change failing): Consider coin denominations and target amount .

• Greedy (local): Pick , then , then → 3 coins.
• Optimal (global): Pick → 2 coins.

Here the greedy locally optimal choice of picking the largest coin fails to reach the global optimum, showing that greedy only works when the greedy choice property holds.

Problem Statement: Given a set of jobs where each job has a deadline and a profit , and each job takes one unit of time, schedule jobs to maximize total profit such that only one job runs at a time and each is completed before its deadline.

Greedy Strategy:

1. Sort all jobs in decreasing order of profit.
2. Initialize a time-slot array of size = maximum deadline, all free.
3. For each job, place it in the latest free slot before or on its deadline.
4. If no free slot exists before the deadline, skip the job.

Example:

• J1 (profit 20, dl 2) → slot 2
• J2 (profit 15, dl 2) → slot 1
• J3 (profit 10, dl 1) → slot 1 full, skip
• J4 (profit 5, dl 3) → slot 3

Selected Jobs: J1, J2, J4 with total profit = 40.

Time Complexity: with array, or using Disjoint Set Union.

Problem Statement: Given activities each with a start time and finish time , select the maximum number of non-overlapping activities that can be performed by a single person.

Greedy Approach:

1. Sort activities by their finish time in increasing order.
2. Select the first activity.
3. For each subsequent activity, select it if its start time is finish time of the last selected activity.

Proof of Optimality (Greedy Choice Property):

• Let activities be sorted so that .
• Claim: There exists an optimal solution that includes activity 1 (the one finishing earliest).
• Suppose an optimal solution starts with activity . Since , we can replace with activity 1 without causing overlap, giving another optimal solution of the same size.
• Thus choosing the earliest-finishing activity is always safe, leaving maximum room for remaining activities.

By optimal substructure, the problem reduces to selecting activities that start after , and induction completes the proof.

Time Complexity: due to sorting.

Fractional Knapsack Problem: Given items each with weight and value , and a knapsack of capacity , maximize the total value where fractions of items may be taken.

Greedy Solution:

1. Compute the value-to-weight ratio for each item.
2. Sort items in decreasing order of this ratio.
3. Add items fully until the knapsack cannot hold the whole item.
4. Add a fraction of the next item to fill remaining capacity.

Example: , items: A(60, 10), B(100, 20), C(120, 30).

• Ratios: A = 6, B = 5, C = 4.
• Take A (10) → value 60, cap left 40.
• Take B (20) → value 100, cap left 20.
• Take of C → value .
• Total = 240.

Difference from 0/1 Knapsack:

Time Complexity: .

Problem Statement: Given ropes of different lengths, connect them into one rope. The cost to connect two ropes equals the sum of their lengths. Find the minimum total cost.

Greedy Insight: Ropes connected earlier get added to the cost more times (like Huffman coding). Hence, always connect the two shortest ropes first so that smaller lengths are repeatedly added, minimizing overall cost.

Why Min-Heap: A min-heap efficiently retrieves the two smallest ropes in time per operation, making the algorithm efficient.

Algorithm:

1. Insert all rope lengths into a min-heap.
2. While more than one rope remains:
   • Extract the two smallest ropes.
   • Add their sum to total cost.
   • Insert the sum back into the heap.
3. Return total cost.

Example: Ropes = .

• Connect 2 + 3 = 5 (cost 5), heap: {4, 5, 6}
• Connect 4 + 5 = 9 (cost 9), heap: {6, 9}
• Connect 6 + 9 = 15 (cost 15)
• Total = 5 + 9 + 15 = 29.

Time Complexity: .

Problem Statement: Given a set of coin denominations and a target amount, find the minimum number of coins needed to make that amount.

Greedy Approach:

1. Sort denominations in decreasing order.
2. Pick the largest coin remaining amount.
3. Subtract it and repeat until the amount becomes zero.

Example (Canonical system): Denominations , amount = 63.

• , remaining 13
• , remaining 3
• , remaining 0
• Total coins = 6.

Conditions for Optimality:

• The greedy method works only for canonical coin systems (like standard currency: 1, 5, 10, 25).
• It fails for non-canonical systems. Example: denominations , amount = 6. Greedy gives coins, but optimal is coins.

For arbitrary denominations, Dynamic Programming must be used to guarantee optimality.

Time Complexity (greedy): after sorting.

Problem Statement: Given an array, find the subset whose product of elements is maximum.

Greedy/Case Analysis:

Let the array contain elements. Track count of negatives, zeros, and product.

Rules:

• Multiply all positive numbers.
• Multiply all negative numbers if their count is even.
• If the count of negatives is odd, exclude the largest (closest to zero) negative number.
• Ignore zeros (they reduce the product to 0).

Special Cases:

1. If array has only one element, the answer is that element itself.
2. If array has a single negative and a zero (e.g., ), the maximum product is .
3. If all elements are zero, the answer is .

Example: Array = .

• Negatives = 3 (odd), so exclude largest negative .
• Product = .

Time Complexity: .

Problem Statement: Given an array of integers, find the subset whose product is minimum.

Case Analysis Logic:

Let negCount = number of negatives, posCount = number of positives, zeroCount = number of zeros.

Rules:

1. If there are no negatives, no zeros, and only one element → return that element.
2. If negCount is even and non-zero: to get a minimum (negative) product, exclude the smallest absolute-value negative so that an odd number of negatives remain, making the product negative.
3. If negCount is odd: multiply all negatives (product is already negative) and all positives.
4. If array has only positives → the minimum single product is the smallest positive element.
5. Zeros are excluded unless doing so leaves an empty valid subset.

Example: Array = .

• Negatives = 3 (odd), so multiply all: .
• Minimum product = -24.

Time Complexity: .

Problem Statement: Given two arrays and each of size , rearrange elements (of one or both) to minimize the sum .

Greedy Strategy:

• Sort array in increasing order.
• Sort array in decreasing order.
• Pair the smallest element of with the largest of , and so on.

Proof (Rearrangement Inequality):
The rearrangement inequality states that for two sequences, the sum of products is:

• Maximum when both are sorted in the same order.
• Minimum when sorted in opposite orders.

So pairing the largest with the smallest minimizes the total product sum.

Example: , .

• Sort ascending:
• Sort descending:
• Sum = .

Time Complexity: .

Problem Statement: Given items of sizes and bins of fixed capacity , pack all items into the minimum number of bins. This is an NP-Hard problem, so greedy heuristics are used for approximate solutions.

Common Greedy Heuristics:

• First Fit (FF): Place each item into the first bin that can accommodate it; open a new bin if none fits.
• Best Fit (BF): Place each item into the bin that leaves the least remaining space.
• Worst Fit (WF): Place item into the bin with the most remaining space.
• First Fit Decreasing (FFD): Sort items in decreasing size, then apply First Fit.

Approximation Quality:

• First Fit and Best Fit use at most bins.
• First Fit Decreasing is better: at most bins.

Example: Items = , bin capacity = 10.

• First Fit: Bin1 = {4, 4, 1, 1} (10), Bin2 = {8, 2} (10) → 2 bins.

Time Complexity: for simple FF/BF, with efficient data structures.

Problem Statement: Given an array of size , find the element that appears more than times (the majority element), if it exists.

Boyer-Moore Voting Algorithm (greedy):
The algorithm works in two phases and uses extra space.

Phase 1 – Candidate Selection:

1. Maintain a candidate and a count = 0.
2. For each element:
   • If count == 0, set candidate = element.
   • If element equals candidate, increment count; else decrement count.

Phase 2 – Verification:

• Count occurrences of the candidate; if greater than , it is the majority element.

Intuition: Each occurrence of a non-majority element cancels out one occurrence of the majority. Since the majority appears more than half the time, it survives all cancellations.

Example: Array = .

• Candidate ends as 2, count verification = 4 > 3 → Majority element = 2.

Time Complexity: , Space Complexity: .

Both greedy and dynamic programming (DP) exploit optimal substructure, but they differ in how they make decisions.

When to prefer Greedy:

• When the greedy choice property is proven (e.g., Activity Selection, Fractional Knapsack, Huffman coding).
• When efficiency is critical and a proof of correctness exists.

When to prefer DP:

• When local choices do not guarantee global optimality (e.g., 0/1 Knapsack, general Coin Change).
• When subproblems overlap and can be memoized.

Key takeaway: Greedy is simpler and faster but must be proven correct; DP is more general and always yields the optimum when applicable.

Step 1 – Sort by decreasing profit:

Step 2 – Maximum deadline = 4, so create 4 slots: [ , , , ].

Step 3 – Assign jobs to latest free slot before deadline:

• J4 (dl 1): slot 1 → [J4, , , _]
• J2 (dl 1): slot 1 full → skip
• J1 (dl 4): slot 4 → [J4, , , J1]
• J5 (dl 3): slot 3 → [J4, _, J5, J1]
• J3 (dl 1): slot 1 full → skip

Step 4 – Selected jobs: J4, J5, J1.

Maximum Profit = .

Scheduled sequence: J4 → (idle) → J5 → J1.

A greedy algorithm is guaranteed to be correct only if the problem exhibits two properties:

1. Greedy Choice Property:

• A globally optimal solution can be arrived at by making a locally optimal (greedy) choice at each step.
• The choice made now does not depend on future choices or solutions to subproblems.
• This lets the algorithm commit to a choice without reconsidering it.

2. Optimal Substructure:

• An optimal solution to the problem contains within it optimal solutions to its subproblems.
• After making the greedy choice, the remaining problem is a smaller instance of the same problem.

Why Both Are Essential:

• Optimal substructure ensures the problem can be broken into subproblems and solved recursively — this alone is shared with DP.
• Greedy choice property additionally ensures we can pick the best local option without exploring all subproblems, which is what makes greedy faster than DP.

If only optimal substructure holds (but not the greedy choice property), DP is required. If the greedy choice property fails, greedy gives a suboptimal result (e.g., 0/1 Knapsack).

Example: In Activity Selection, choosing the earliest finishing activity (greedy choice) always leaves an optimal subproblem (optimal substructure), so greedy is provably correct.

Though both involve scheduling tasks, they optimize different objectives and use different greedy criteria.

Job Sequencing: Every job needs one time slot; conflicting jobs compete for slots, so we prioritize higher-profit jobs.

Activity Selection: Activities have durations; overlapping ones cannot be chosen together, so we maximize count by freeing up time as early as possible.

Common ground: Both are classic greedy problems that require sorting and iterative selection.

Step 1 – Compute value-to-weight ratios:

Step 2 – Sort by decreasing ratio: Item3 (8), Item2 (7), Item1 (5), Item4 (3).

Step 3 – Fill knapsack (W = 15):

• Item3 (w 5): take fully → value 40, remaining capacity = 10.
• Item2 (w 3): take fully → value 21, remaining capacity = 7.
• Item1 (w 6): take fully → value 30, remaining capacity = 1.
• Item4 (w 4): take fraction → value , remaining = 0.

Step 4 – Total value:

Total weight used = 15 (full capacity). Maximum achievable value = 94.

Connect n Ropes Recap: Repeatedly connect the two shortest ropes (using a min-heap) until one rope remains, minimizing total connection cost.

Relationship with Huffman Coding:
Both problems share the same underlying greedy structure:

• In Huffman coding, we repeatedly merge the two least-frequent symbols into a subtree, minimizing the weighted path length (frequency × depth).
• In Connect Ropes, we repeatedly merge the two shortest ropes, minimizing .

Mapping:

Key Insight: In both, elements combined earlier contribute to the cost more times (they sit deeper in the merge tree). Combining smallest elements first ensures small values are added repeatedly, minimizing the total — this is the essence of the optimal merge pattern.

Time Complexity: for both.

Greedy Algorithm General Template:

1. Sort/prioritize candidates by a greedy criterion.
2. Iterate; at each step pick the locally best candidate that satisfies constraints.
3. Commit permanently (no backtracking).

This works for problems like Fractional Knapsack and Activity Selection because they satisfy the greedy choice property.

Limitations of Greedy Algorithms:
Greedy does not always yield the global optimum. Failures occur when a locally optimal choice blocks a better global solution.

Example 1 – 0/1 Knapsack:

• Capacity = 10; items: A(w 6, v 30, ratio 5), B(w 5, v 25, ratio 5), C(w 5, v 25, ratio 5).
• Greedy by ratio picks A first (value 30), then cannot fit B or C fully → value 30.
• Optimal: B + C = value 50.
• Greedy fails because items cannot be split.

Example 2 – Coin Change with , amount 6:

• Greedy: coins.
• Optimal: coins.
• Greedy fails for non-canonical denominations.

Conclusion: Always prove the greedy choice property before trusting a greedy solution; otherwise use Dynamic Programming.

In competitive programming, greedy techniques are prized for their simplicity and speed, but they must be applied carefully.

General Strategy:

1. Identify the objective (maximize/minimize something).
2. Guess a greedy criterion (e.g., smallest first, largest ratio, earliest deadline).
3. Test with examples, especially edge cases and counterexamples.
4. Prove correctness using the greedy choice property (often via an exchange argument).
5. Implement efficiently — typically sorting + a single pass, or a priority queue.

How to Recognize a Greedy Problem:

• The problem asks for an optimum (max/min) and choices can be made step by step.
• A local choice never needs to be undone (no backtracking helps).
• The problem has optimal substructure.
• Sorting the input by some key seems to naturally lead toward the answer.

Common Greedy Problem Signatures:

• Scheduling with deadlines → sort by profit/deadline.
• Interval selection → sort by finish time.
• Merging/combining costs → use a min-heap.
• Ratio-based selection → Fractional Knapsack style.

Proof Technique – Exchange Argument: Assume an optimal solution differs from the greedy one; show you can swap elements to match the greedy choice without worsening the result, proving greedy is at least as good.

Caution: Always verify with counterexamples. If greedy fails, switch to Dynamic Programming or another paradigm.