Why Greedy Works and When It Fails in DSA Typescript - See It Work

Why Greedy Works and When It Fails

📖 Scenario: Imagine you are organizing a small event and need to select tasks to complete within a limited time. Each task has a duration and a value representing its importance. You want to pick tasks to maximize total importance without exceeding the available time.This project will help you understand how a greedy approach can work well in some cases and fail in others.

🎯 Goal: You will build a simple program that selects tasks using a greedy method based on task duration. Then, you will see when this approach fails and why.

📋 What You'll Learn

Create an array of tasks with exact durations and values

Set a total available time limit

Implement a greedy selection of tasks by shortest duration first

Print the selected tasks and total value

💡 Why This Matters

🌍 Real World

Task scheduling and resource allocation often use greedy methods for quick decisions.

💼 Career

Understanding when greedy algorithms work or fail helps in software engineering, operations research, and optimization roles.

1

Create the tasks array

Create an array called tasks with these exact objects: {name: 'Task1', duration: 1, value: 10}, {name: 'Task2', duration: 3, value: 20}, {name: 'Task3', duration: 2, value: 15}, {name: 'Task4', duration: 4, value: 40}.

DSA Typescript

# Your code here

Hint

Use an array of objects with keys name, duration, and value.

2

Set the total available time

Create a variable called totalTime and set it to 5 to represent the total available time for tasks.

DSA Typescript

const tasks = [
  {name: 'Task1', duration: 1, value: 10},
  {name: 'Task2', duration: 3, value: 20},
  {name: 'Task3', duration: 2, value: 15},
  {name: 'Task4', duration: 4, value: 40}
];
// Your code here

Hint

Use const totalTime = 5; to set the time limit.

3

Select tasks greedily by shortest duration

Create a variable called selectedTasks as an empty array. Use tasks.sort((a, b) => a.duration - b.duration) to sort tasks by duration ascending. Then use a for loop with variable task over tasks. Keep track of usedTime starting at 0. For each task, if usedTime + task.duration <= totalTime, add task to selectedTasks and add task.duration to usedTime.

DSA Typescript

const tasks = [
  {name: 'Task1', duration: 1, value: 10},
  {name: 'Task2', duration: 3, value: 20},
  {name: 'Task3', duration: 2, value: 15},
  {name: 'Task4', duration: 4, value: 40}
];

const totalTime = 5;

// Your code here

Hint

Sort tasks by duration, then pick tasks while total time allows.

4

Print selected tasks and total value

Print the names of tasks in selectedTasks separated by commas using console.log. Then print the total value of selected tasks by summing task.value for each task in selectedTasks.

DSA Typescript

const tasks = [
  {name: 'Task1', duration: 1, value: 10},
  {name: 'Task2', duration: 3, value: 20},
  {name: 'Task3', duration: 2, value: 15},
  {name: 'Task4', duration: 4, value: 40}
];

const totalTime = 5;

const selectedTasks = [];
tasks.sort((a, b) => a.duration - b.duration);
let usedTime = 0;
for (const task of tasks) {
  if (usedTime + task.duration <= totalTime) {
    selectedTasks.push(task);
    usedTime += task.duration;
  }
}

// Your code here

Hint

Use map and join to print names, and reduce to sum values.

Practice

1. What is the main reason a greedy algorithm works correctly for some problems?

easy

A. Because it tries all possible solutions and picks the best one

B. Because it uses recursion to explore all paths

C. Because it makes the best choice at each step hoping for a global optimum

D. Because it sorts the input data before processing

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm picks the best local option at each step without reconsidering previous choices.

2. Step 2: Connect local choices to global optimum

   For some problems, these local best choices lead to the overall best solution, which is why greedy works.

3. Final Answer:

   Because it makes the best choice at each step hoping for a global optimum -> Option C

4. Quick Check:

   Greedy = best local choice each step [OK]

Hint: Greedy picks best now, hoping for best overall [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with recursion
• Assuming sorting always means greedy

2. Which of the following is the correct syntax to start a greedy algorithm loop in TypeScript to process an array arr?

easy

A. for (let i = 0; i < arr.length; i++) { /* greedy step */ }

B. while (arr.length) { /* greedy step */ }

C. for (const i in arr) { /* greedy step */ }

D. do { /* greedy step */ } while (arr.length)

Solution

1. Step 1: Identify standard for loop syntax

   The standard way to iterate over an array with index in TypeScript is using for (let i = 0; i < arr.length; i++).

2. Step 2: Check other options for correctness

   while (arr.length) { /* greedy step */ } and D use while/do-while but lack index control; for (const i in arr) { /* greedy step */ } uses for...in which iterates keys but is less common and can cause issues.

3. Final Answer:

   for (let i = 0; i < arr.length; i++) { /* greedy step */ } -> Option A

4. Quick Check:

   Standard for loop = for (let i = 0; i < arr.length; i++) { /* greedy step */ } [OK]

Hint: Use for(let i=0; i

Common Mistakes:

• Using for...in for arrays causing unexpected keys
• Missing loop condition causing infinite loops
• Using while without index control

3. Consider the following TypeScript code for selecting intervals greedily by earliest finish time:

const intervals = [[1,4],[3,5],[0,6],[5,7],[8,9],[5,9]];
intervals.sort((a,b) => a[1] - b[1]);
let count = 0;
let end = -Infinity;
for (const [start, finish] of intervals) {
  if (start >= end) {
    count++;
    end = finish;
  }
}
console.log(count);

What is the output?

medium

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals: [1,4], [3,5], [0,6], [5,7], [8,9], [5,9]

2. Step 2: Select intervals greedily

   Start with end = -Infinity.
   Pick [1,4] (start 1 >= -Infinity), count=1, end=4.
   Next [3,5] start 3 < 4 skip.
   Next [0,6] start 0 < 4 skip.
   Next [5,7] start 5 >= 4 pick, count=2, end=7.
   Next [8,9] start 8 >= 7 pick, count=3, end=9.
   Next [5,9] start 5 < 9 skip.

3. Step 3: Count total selected intervals

   Total count = 3

4. Final Answer:

   3 -> Option B

5. Quick Check:

   Greedy interval count = 3 [OK]

Hint: Sort by finish time, pick non-overlapping intervals [OK]

Common Mistakes:

• Not sorting intervals by finish time
• Counting overlapping intervals
• Updating end incorrectly

4. The following code attempts to solve the coin change problem greedily by always picking the largest coin first:

const coins = [25, 10, 5, 1];
function greedyChange(amount: number): number {
  let count = 0;
  for (const coin of coins) {
    count += Math.floor(amount / coin);
    amount %= coin;
  }
  return count;
}
console.log(greedyChange(30));

What is the output and what is the bug if any?

medium

A. 6; Bug: code does not reduce amount correctly

B. 3; Bug: greedy fails for some coin sets

C. Error; Syntax mistake in code

D. 2; No bug, greedy works for US coins

Solution

1. Step 1: Trace greedyChange(30)

   Coins: 25,10,5,1
   25 fits once (30/25=1), count=1, amount=30%25=5
   10 fits zero times (5/10=0), count=1, amount=5
   5 fits once (5/5=1), count=2, amount=0
   1 fits zero times, count=2

2. Step 2: Check if greedy works here

   For US coins, greedy always gives minimum coins. So output is 2 and no bug here.

3. Final Answer:

   2; No bug, greedy works for US coins -> Option D

4. Quick Check:

   Greedy coin change = 2 [OK]

Hint: Greedy coin works for standard US coins [OK]

Common Mistakes:

• Assuming greedy always fails coin change
• Miscomputing amount after division
• Confusing output count with amount

5. You want to select activities from a list with start and end times to maximize the number of activities chosen. However, the activities have a penalty cost if chosen consecutively. Which approach best solves this problem?

hard

A. Use dynamic programming to consider penalties and maximize total benefit

B. Use brute force to try all subsets without pruning

C. Sort activities by start time and pick all that fit ignoring penalties

D. Use a greedy algorithm selecting earliest finishing activities ignoring penalties

Solution

1. Step 1: Understand problem constraints

   Activities have penalties if chosen consecutively, so simple greedy ignoring penalties may fail.

2. Step 2: Choose algorithm considering penalties

   Dynamic programming can track choices and penalties to find maximum benefit, unlike greedy which only looks locally.

3. Final Answer:

   Use dynamic programming to consider penalties and maximize total benefit -> Option A

4. Quick Check:

   Penalties require DP, not greedy [OK]

Hint: Penalties break greedy; use DP for best solution [OK]

Common Mistakes:

• Ignoring penalties and using greedy
• Assuming sorting by start time is enough
• Trying brute force without pruning