Activity Selection Problem in DSA Go - Build from Scratch

Activity Selection Problem

📖 Scenario: You are organizing a conference with many talks. Each talk has a start time and an end time. You want to attend the maximum number of talks without any overlaps.

🎯 Goal: Build a program that selects the maximum number of non-overlapping activities (talks) you can attend.

📋 What You'll Learn

Create a list of activities with start and end times

Sort activities by their end times

Select the maximum number of activities that do not overlap

Print the selected activities in order

💡 Why This Matters

🌍 Real World

Scheduling meetings, talks, or tasks without conflicts is common in event planning and project management.

💼 Career

Understanding greedy algorithms and interval scheduling is useful for software engineers working on calendar apps, resource allocation, and optimization problems.

1

Create the list of activities

Create a slice of structs called activities with these exact entries: {start: 1, end: 4}, {start: 3, end: 5}, {start: 0, end: 6}, {start: 5, end: 7}, {start: 8, end: 9}, {start: 5, end: 9}

DSA Go

// Define the Activity struct and create the activities slice
// Your code here

Hint

Define a struct named Activity with start and end fields of type int. Then create a slice named activities with the given values.

2

Sort activities by their end times

Import the sort package and sort the activities slice by the end field in ascending order using sort.Slice

DSA Go

package main

import (
    "fmt"
    "sort"
)

type Activity struct {
    start int
    end   int
}

func main() {
    activities := []Activity{
        {start: 1, end: 4},
        {start: 3, end: 5},
        {start: 0, end: 6},
        {start: 5, end: 7},
        {start: 8, end: 9},
        {start: 5, end: 9},
    }
    // Sort activities by end time
    // Your code here
}

Hint

Use sort.Slice with a function comparing the end fields of activities at indices i and j.

3

Select the maximum number of non-overlapping activities

Create a slice called selected to store chosen activities. Add the first activity from activities to selected. Then use a for loop with variable i from 1 to len(activities)-1. Inside the loop, if activities[i].start is greater or equal to the end of the last selected activity, append activities[i] to selected

DSA Go

package main

import (
    "fmt"
    "sort"
)

type Activity struct {
    start int
    end   int
}

func main() {
    activities := []Activity{
        {start: 1, end: 4},
        {start: 3, end: 5},
        {start: 0, end: 6},
        {start: 5, end: 7},
        {start: 8, end: 9},
        {start: 5, end: 9},
    }

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

    // Select activities
    // Your code here
}

Hint

Start with the first activity in selected. Then loop through the rest and add an activity only if its start time is after or equal to the last selected activity's end time.

4

Print the selected activities

Use a for loop with variable _, activity to iterate over selected. Inside the loop, print the activity's start and end times in the format "Activity: start X, end Y"

DSA Go

package main

import (
    "fmt"
    "sort"
)

type Activity struct {
    start int
    end   int
}

func main() {
    activities := []Activity{
        {start: 1, end: 4},
        {start: 3, end: 5},
        {start: 0, end: 6},
        {start: 5, end: 7},
        {start: 8, end: 9},
        {start: 5, end: 9},
    }

    sort.Slice(activities, func(i, j int) bool {
        return activities[i].end = lastEnd {
            selected = append(selected, activities[i])
            lastEnd = activities[i].end
        }
    }

    // Print selected activities
    // Your code here
}

Hint

Loop over selected and print each activity's start and end times using fmt.Printf with the format "Activity: start %d, end %d\n".

Practice

1. What is the main goal of the Activity Selection Problem?

easy

A. Find the activity with the longest duration

B. Sort activities by their start times

C. Select the maximum number of activities that don't overlap

D. Calculate the total time of all activities

Solution

1. Step 1: Understand the problem goal

   The Activity Selection Problem aims to choose activities that do not overlap in time.

2. Step 2: Identify the objective

   The objective is to select the maximum number of such non-overlapping activities.

3. Final Answer:

   Select the maximum number of activities that don't overlap -> Option C

4. Quick Check:

   Goal = Max non-overlapping activities [OK]

Hint: Pick activities with earliest finish times first [OK]

Common Mistakes:

• Choosing activities based on longest duration
• Sorting by start time only
• Trying to maximize total duration instead of count

2. Which of the following Go code snippets correctly sorts activities by their finish time for the Activity Selection Problem?

easy

A. sort.Ints(activities)

B. sort.Slice(activities, func(i, j int) bool { return activities[i].start < activities[j].start })

C. sort.Sort(activities)

D. sort.Slice(activities, func(i, j int) bool { return activities[i].finish < activities[j].finish })

Solution

1. Step 1: Identify sorting criteria

   Activities must be sorted by their finish time to apply the greedy approach.

2. Step 2: Check Go sorting syntax

   Using sort.Slice with a comparison function on finish times is correct.

3. Final Answer:

   sort.Slice(activities, func(i, j int) bool { return activities[i].finish < activities[j].finish }) -> Option D

4. Quick Check:

   Sort by finish time = sort.Slice(activities, func(i, j int) bool { return activities[i].finish < activities[j].finish }) [OK]

Hint: Sort activities by finish time using sort.Slice [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Using sort.Ints on struct slices
• Calling sort.Sort without implementing sort.Interface

3. What is the output of the following Go code snippet that implements the Activity Selection Problem?

package main
import (
  "fmt"
  "sort"
)
type Activity struct {
  start, finish int
}
func main() {
  activities := []Activity{{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}}
  sort.Slice(activities, func(i, j int) bool { return activities[i].finish < activities[j].finish })
  count := 1
  lastFinish := activities[0].finish
  for i := 1; i < len(activities); i++ {
    if activities[i].start >= lastFinish {
      count++
      lastFinish = activities[i].finish
    }
  }
  fmt.Println(count)
}

medium

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Sort activities by finish time

   Sorted activities by finish: (1,4), (3,5), (0,6), (5,7), (8,9), (5,9)

2. Step 2: Select activities greedily

   Select (1,4), next (5,7) since 5 >= 4, then (8,9) since 8 >= 7. Total selected = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Max non-overlapping = 3 [OK]

Hint: Count activities with start >= last selected finish [OK]

Common Mistakes:

• Counting overlapping activities
• Not sorting by finish time
• Starting count from zero instead of one

4. Identify the bug in this Go code snippet for the Activity Selection Problem:

package main
import (
  "fmt"
  "sort"
)
type Activity struct {
  start, finish int
}
func main() {
  activities := []Activity{{1, 3}, {2, 5}, {4, 7}}
  sort.Slice(activities, func(i, j int) bool { return activities[i].start < activities[j].start })
  count := 1
  lastFinish := activities[0].finish
  for i := 1; i < len(activities); i++ {
    if activities[i].start >= lastFinish {
      count++
      lastFinish = activities[i].finish
    }
  }
  fmt.Println(count)
}

medium

A. Sorting by start time instead of finish time

B. Initializing count to zero instead of one

C. Using wrong comparison operator in if condition

D. Not importing the fmt package

Solution

1. Step 1: Check sorting criteria

   The code sorts activities by start time, but the greedy approach requires sorting by finish time.

2. Step 2: Understand impact of sorting

   Sorting by start time can cause incorrect selection of activities, leading to wrong count.

3. Final Answer:

   Sorting by start time instead of finish time -> Option A

4. Quick Check:

   Sort by finish time needed [OK]

Hint: Always sort by finish time, not start time [OK]

Common Mistakes:

• Sorting by start time
• Forgetting to update lastFinish
• Starting count at zero

5. Given the following activities with start and finish times: [(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)], what is the maximum number of activities that can be selected without overlap using the Activity Selection Problem approach?

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Sort activities by finish time

   Sorted activities: (1,2), (3,4), (0,6), (5,7), (8,9), (5,9)

2. Step 2: Select activities greedily

   Select (1,2), then (3,4) since 3 >= 2, then (5,7) since 5 >= 4, then (8,9) since 8 >= 7. Total selected = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Max non-overlapping = 4 [OK]

Hint: Pick earliest finishing activities that start after last finish [OK]

Common Mistakes:

• Including overlapping activities
• Not sorting by finish time
• Counting all activities without checking overlap