Activity Selection Problem in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort activities by their finish time.

DSA Go

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

Drag options to blanks, or click blank then click option'

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' causes sorting in descending order.

Using '==' or '!=' does not sort properly.

We sort activities by their finish time in ascending order to select the earliest finishing activity first.

2fill in blank

medium

Complete the code to select the first activity after sorting.

DSA Go

selected := []Activity{activities[[1]]}

Drag options to blanks, or click blank then click option'

A1

B0

C-1

Dlen(activities)

Attempts:

3 left

💡 Hint

Common Mistakes

Using index 1 skips the first activity.

Using -1 or len(activities) causes runtime errors.

The first activity after sorting is at index 0.

3fill in blank

hard

Fix the error in the loop condition to select compatible activities.

DSA Go

for i := 1; i < [1]; i++ {
    if activities[i].start >= selected[len(selected)-1].finish {
        selected = append(selected, activities[i])
    }
}

Drag options to blanks, or click blank then click option'

Acap(activities)

Bactivities

Cselected

Dlen(activities)

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'activities' directly causes a compile error.

Using 'selected' limits the loop incorrectly.

Using cap(activities) may cause incomplete iteration.

We loop through all activities using their length to avoid index errors.

4fill in blank

hard

Fill both blanks to define the Activity struct and initialize activities slice.

DSA Go

type Activity struct {
    start  int
    [1] int
}

activities := []Activity{{
    {start: 1, [2]: 4},
    {start: 3, finish: 5},
    {start: 0, finish: 6},
}}

Drag options to blanks, or click blank then click option'

Afinish

Bend

Cduration

Dtime

Attempts:

3 left

💡 Hint

Common Mistakes

Using different field names causes compile errors.

Using 'end' or 'duration' instead of 'finish' breaks the logic.

The field name must be 'finish' to match usage in code and initialization.

5fill in blank

hard

Fill all three blanks to print the selected activities' start and finish times.

DSA Go

for _, act := range selected {
    fmt.Println("Activity:", [1], "to", [2])
}

// To print the number of selected activities
fmt.Println("Total selected:", [3])

Drag options to blanks, or click blank then click option'

Aact.start

Bact.finish

Clen(selected)

Dselected

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'selected' instead of 'len(selected)' prints the slice, not count.

Mixing up start and finish fields in print statements.

We print start and finish fields of each activity and the total count using len(selected).

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