Activity Selection Problem in DSA Go - Execution Trace

Concept Flow - Activity Selection Problem

Sort activities by finish time

↓

Select first activity

↓

For each next activity

↓

Check if start >= last selected finish

↓

Select activity

↓

Repeat until all activities checked

↓

Done

Sort activities by finish time, then pick the earliest finishing activity that starts after the last selected one, repeat until all are checked.

Execution Sample

DSA Go

activities := []Activity{{1,4},{3,5},{0,6},{5,7},{3,9},{5,9},{6,10},{8,11},{8,12},{2,14},{12,16}}
sort.Slice(activities, func(i, j int) bool { return activities[i].finish < activities[j].finish })
selected := []Activity{activities[0]}
for i := 1; i < len(activities); i++ {
    if activities[i].start >= selected[len(selected)-1].finish {
        selected = append(selected, activities[i])
    }
}

Select maximum number of activities that don't overlap by sorting and greedy selection.

Execution Table

Step	Operation	Selected Activities	Current Activity	Condition (start >= last finish?)	Action	Visual State
1	Sort activities by finish time	[]	N/A	N/A	Sorted activities	[{1,4}, {3,5}, {0,6}, {5,7}, {3,9}, {5,9}, {6,10}, {8,11}, {8,12}, {2,14}, {12,16}]
2	Select first activity	[{1,4}]	{1,4}	N/A	Select	[{1,4}]
3	Check activity	[{1,4}]	{3,5}	3 >= 4? False	Skip	[{1,4}]
4	Check activity	[{1,4}]	{0,6}	0 >= 4? False	Skip	[{1,4}]
5	Check activity	[{1,4}]	{5,7}	5 >= 4? True	Select	[{1,4}, {5,7}]
6	Check activity	[{1,4}, {5,7}]	{3,9}	3 >= 7? False	Skip	[{1,4}, {5,7}]
7	Check activity	[{1,4}, {5,7}]	{5,9}	5 >= 7? False	Skip	[{1,4}, {5,7}]
8	Check activity	[{1,4}, {5,7}]	{6,10}	6 >= 7? False	Skip	[{1,4}, {5,7}]
9	Check activity	[{1,4}, {5,7}]	{8,11}	8 >= 7? True	Select	[{1,4}, {5,7}, {8,11}]
10	Check activity	[{1,4}, {5,7}, {8,11}]	{8,12}	8 >= 11? False	Skip	[{1,4}, {5,7}, {8,11}]
11	Check activity	[{1,4}, {5,7}, {8,11}]	{2,14}	2 >= 11? False	Skip	[{1,4}, {5,7}, {8,11}]
12	Check activity	[{1,4}, {5,7}, {8,11}]	{12,16}	12 >= 11? True	Select	[{1,4}, {5,7}, {8,11}, {12,16}]
13	All activities checked	[{1,4}, {5,7}, {8,11}, {12,16}]	N/A	N/A	Done	[{1,4}, {5,7}, {8,11}, {12,16}]

💡 All activities checked, no more to select

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 12	Final
Selected Activities	[]	[{1,4}]	[{1,4}, {5,7}]	[{1,4}, {5,7}, {8,11}]	[{1,4}, {5,7}, {8,11}, {12,16}]	[{1,4}, {5,7}, {8,11}, {12,16}]
Current Activity	N/A	{3,5}	{5,7}	{8,11}	{12,16}	N/A
Last Selected Finish Time	N/A	4	7	11	16	16

Key Moments - 3 Insights

Why do we sort activities by finish time first?

Sorting by finish time ensures we always pick the activity that frees the schedule earliest, allowing more activities to fit later. See execution_table step 1 where sorting happens before selection.

Why do we skip activities that start before the last selected activity finishes?

Because they overlap and can't be done together. For example, in step 3, activity {3,5} starts before last finish 4, so it's skipped.

Why do we select the first activity without checking any condition?

Because after sorting, the first activity finishes earliest, so it's always safe to select it. See step 2 in execution_table.

Visual Quiz - 3 Questions

Look at the execution table, what is the selected activities list after step 5?

A [{1,4}, {3,5}]

B [{1,4}, {5,7}]

C [{1,4}, {0,6}]

D [{3,5}, {5,7}]

💡 Hint

Check the 'Selected Activities' column at step 5 in the execution_table.

At which step does the condition 'start >= last finish' become false for activity {3,5}?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Condition' column for activity {3,5} in execution_table step 3.

If the activity {8,12} had start time 12 instead of 8, what would happen at step 10?

A It would be skipped

B Algorithm would stop

C It would be selected

D It would replace {8,11}

💡 Hint

Check condition 'start >= last finish' at step 10 and compare with last selected finish time.

Concept Snapshot

Activity Selection Problem:
- Sort activities by finish time
- Select first activity
- For each next activity:
  - If start >= last selected finish, select it
- Repeat until all checked
- Result: max non-overlapping activities

Full Transcript

The Activity Selection Problem finds the maximum number of activities that don't overlap. First, activities are sorted by their finish times. Then, the earliest finishing activity is selected. For each next activity, if its start time is equal or after the last selected activity's finish time, it is selected; otherwise, it is skipped. This process continues until all activities are checked. The final selected list contains the maximum number of compatible activities.

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