🧠 Week 2: Greedy Algorithms

📌 What is a Greedy Algorithm?

A greedy algorithm is a simple and efficient approach for solving optimization problems by making the locally optimal choice at each step with the hope that these choices will lead to a globally optimal solution.

✅ Key Characteristics

• It does not explore the entire search space like brute-force or complete search.
• It works only if the greedy choice property and optimal substructure are satisfied.
• In each step, it selects the best option available at that moment.

📖 Example Problem

You are given N tasks, and for each task, you know its duration in minutes.

You also have only M free minutes.

Goal: Finish as many tasks as possible.

❌ Brute Force Solution

• Generate all possible subsets of tasks (i.e., the power set).
• For each subset, check if the total duration is within M minutes.
• Track the subset that gives the maximum number of tasks.

Time Complexity: