Why Greedy Works and When It Fails in DSA Go - 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 your available time.This project will help you understand when a simple greedy approach works and when it can fail.

🎯 Goal: You will build a Go program that selects tasks using a greedy method based on task duration. You will see the output of selected tasks and learn why this method sometimes fails to give the best total importance.

📋 What You'll Learn

Create a slice of tasks with exact durations and importance values

Add a time limit variable for total available time

Implement a greedy selection picking tasks with shortest duration first

Print the selected tasks and their total importance

💡 Why This Matters

🌍 Real World

This project models how to select tasks or jobs under time constraints, a common problem in scheduling and resource management.

💼 Career

Understanding greedy algorithms and their limitations is important for software engineers working on optimization, scheduling, and decision-making systems.

1

Create the tasks slice

Create a slice called tasks of structs with fields name (string), duration (int), and importance (int). Add these exact tasks: {"Task1", 3, 5}, {"Task2", 1, 1}, {"Task3", 2, 8}, {"Task4", 5, 4}.

DSA Go

// Your code here to create the tasks slice

Hint

Define a struct Task with the fields name, duration, and importance. Then create a slice tasks with the given values.

2

Add the time limit variable

Add an integer variable called timeLimit and set it to 5 to represent the total available time.

DSA Go

package main

type Task struct {
    name       string
    duration   int
    importance int
}

func main() {
    tasks := []Task{
        {"Task1", 3, 5},
        {"Task2", 1, 1},
        {"Task3", 2, 8},
        {"Task4", 5, 4},
    }
    // Add timeLimit variable here
    // Your code here
}

Hint

Just add timeLimit := 5 inside the main function after creating the tasks slice.

3

Select tasks greedily by shortest duration

Sort the tasks slice by duration in ascending order. Then use a for loop with variable i to iterate over tasks. Keep track of total time used in usedTime starting at 0. For each task, if usedTime + tasks[i].duration <= timeLimit, add the task to a new slice called selected and update usedTime by adding tasks[i].duration. Stop when no more tasks fit.

DSA Go

package main

import "sort"

type Task struct {
    name       string
    duration   int
    importance int
}

func main() {
    tasks := []Task{
        {"Task1", 3, 5},
        {"Task2", 1, 1},
        {"Task3", 2, 8},
        {"Task4", 5, 4},
    }
    timeLimit := 5

    // Sort tasks by duration
    // Your code here

    // Select tasks greedily
    // Your code here
}

Hint

Use sort.Slice to sort by duration. Then loop through tasks with for i := 0; i < len(tasks); i++. Keep track of usedTime and append tasks to selected if they fit.

4

Print selected tasks and total importance

Use a for loop with variable _, task to iterate over selected. Print each task's name and duration. Then calculate the sum of importance of all selected tasks in a variable called totalImportance and print it.

DSA Go

package main

import (
    "fmt"
    "sort"
)

type Task struct {
    name       string
    duration   int
    importance int
}

func main() {
    tasks := []Task{
        {"Task1", 3, 5},
        {"Task2", 1, 1},
        {"Task3", 2, 8},
        {"Task4", 5, 4},
    }
    timeLimit := 5

    sort.Slice(tasks, func(i, j int) bool {
        return tasks[i].duration < tasks[j].duration
    })

    var selected []Task
    usedTime := 0
    for i := 0; i < len(tasks); i++ {
        if usedTime+tasks[i].duration <= timeLimit {
            selected = append(selected, tasks[i])
            usedTime += tasks[i].duration
        } else {
            break
        }
    }

    // Print selected tasks and total importance
    // Your code here
}

Hint

Loop over selected tasks and print their name and duration. Sum their importance in totalImportance and print it.

Practice

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

easy

A. Because it sorts the input data before processing

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

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

D. Because it uses recursion to explore all paths

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm makes the best local choice at each step, aiming for a global best solution.

2. Step 2: Differentiate from exhaustive search

   Unlike trying all solutions or recursion, greedy does not explore all paths but relies on local optimality.

3. Final Answer:

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

4. Quick Check:

   Greedy choice property = Because it makes the best choice at each step hoping for a global optimum [OK]

Hint: Greedy picks best local choice, not all possibilities [OK]

Common Mistakes:

• Confusing greedy with exhaustive search
• Thinking greedy always tries all solutions
• Assuming sorting alone makes greedy correct

2. Which of the following Go code snippets correctly implements a greedy step to pick the largest number from a slice?

easy

A. max := nums[0]
for _, v := range nums {
if v > max {
max = v
}
}

B. max := 0
for i := 1; i < len(nums); i++ {
if nums[i] < max {
max = nums[i]
}
}

C. max := nums[0]
for i := 0; i < len(nums); i++ {
if nums[i] < max {
max = nums[i]
}
}

D. max := nums[0]
for _, v := range nums {
if v < max {
max = v
}
}

Solution

1. Step 1: Identify correct max initialization and comparison

   Initialize max with first element and update if current value is greater.

2. Step 2: Check loop and condition correctness

   max := nums[0] for _, v := range nums { if v > max { max = v } } uses correct range loop and updates max when v > max.

3. Final Answer:

   Option A correctly finds the largest number -> Option A

4. Quick Check:

   Correct max update condition = max := nums[0] for _, v := range nums { if v > max { max = v } } [OK]

Hint: Update max only if current value is greater [OK]

Common Mistakes:

• Using '<' instead of '>' to find max
• Initializing max to zero instead of first element
• Comparing incorrectly inside loop

3. What will be the output of the following Go code that tries to select intervals greedily by earliest finish time?

package main
import "fmt"
func main() {
  intervals := [][]int{{1,4},{3,5},{0,6},{5,7},{8,9},{5,9}}
  selected := [][]int{}
  lastEnd := 0
  for _, interval := range intervals {
    if interval[0] >= lastEnd {
      selected = append(selected, interval)
      lastEnd = interval[1]
    }
  }
  fmt.Println(selected)
}

medium

A. [[1 4] [5 7] [8 9]]

B. [[1 4] [3 5] [5 7] [8 9]]

C. [[0 6] [8 9]]

D. [[1 4] [5 9]]

Solution

1. Step 1: Understand greedy selection by earliest finish time

   Intervals are checked in given order; select if start >= last selected end.

2. Step 2: Trace selection step-by-step

   Selected intervals: [1,4] (lastEnd=4), skip [3,5], skip [0,6], select [5,7] (lastEnd=7), select [8,9].

3. Final Answer:

   [[1 4] [5 7] [8 9]] -> Option A

4. Quick Check:

   Greedy interval selection = [[1 4] [5 7] [8 9]] [OK]

Hint: Pick intervals starting after last end time [OK]

Common Mistakes:

• Not updating lastEnd correctly
• Selecting overlapping intervals
• Assuming input is sorted by finish time

4. The following Go code tries to solve the coin change problem greedily but sometimes fails. What is the bug?

package main
import "fmt"
func main() {
  coins := []int{25, 10, 5, 1}
  amount := 30
  count := 0
  for _, coin := range coins {
    count += amount / coin
    amount = amount % coin
  }
  fmt.Println(count)
}

medium

A. The coins slice is not sorted in ascending order

B. The greedy approach fails for some coin sets, but code logic is correct

C. The code does not update amount correctly inside the loop

D. The count variable should be reset inside the loop

Solution

1. Step 1: Analyze greedy coin change logic

   The code picks largest coins first, counting how many fit, updating amount correctly.

2. Step 2: Understand greedy failure cases

   Greedy works for US coins but fails for some coin sets; code logic is correct but approach can fail.

3. Final Answer:

   The greedy approach fails for some coin sets, but code logic is correct -> Option B

4. Quick Check:

   Greedy correctness depends on coin set = The greedy approach fails for some coin sets, but code logic is correct [OK]

Hint: Greedy coin change fails on non-canonical coin sets [OK]

Common Mistakes:

• Thinking code has syntax or logic error
• Assuming coin order must be ascending
• Resetting count inside loop incorrectly

5. You want to schedule the maximum number of non-overlapping meetings from a list of start and end times. Which greedy strategy guarantees the optimal solution?

hard

A. Always pick the meeting with the latest start time

B. Always pick the meeting with the shortest duration

C. Always pick the meeting with the earliest start time

D. Always pick the meeting with the earliest finish time

Solution

1. Step 1: Recall interval scheduling greedy strategy

   The proven greedy method is to pick meetings finishing earliest to maximize remaining time.

2. Step 2: Compare other strategies

   Picking earliest start or shortest duration can cause overlaps and miss optimal count.

3. Final Answer:

   Always pick the meeting with the earliest finish time -> Option D

4. Quick Check:

   Earliest finish time strategy = Always pick the meeting with the earliest finish time [OK]

Hint: Pick meetings finishing earliest to maximize schedule [OK]

Common Mistakes:

• Choosing earliest start time instead of finish time
• Picking shortest duration meetings incorrectly
• Assuming latest start time works best