Activity Selection Problem in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Activity Selection with Overlapping Activities

What is the output of the following Go code that selects the maximum number of non-overlapping activities?

DSA Go

package main
import "fmt"

func activitySelection(start []int, end []int) []int {
    n := len(start)
    selected := []int{0}
    lastEnd := end[0]
    for i := 1; i < n; i++ {
        if start[i] >= lastEnd {
            selected = append(selected, i)
            lastEnd = end[i]
        }
    }
    return selected
}

func main() {
    start := []int{1, 3, 0, 5, 8, 5}
    end := []int{2, 4, 6, 7, 9, 9}
    result := activitySelection(start, end)
    fmt.Println(result)
}

A [0 1 4]

B [0 2 3 5]

C [1 3 4]

D [0 1 3 4]

💡 Hint

Remember that activities must be sorted by their finish times for the greedy approach to work correctly.

The code assumes activities are sorted by their end times. It selects the first activity, then picks the next activity whose start time is not less than the last selected activity's end time. The selected indices are 0, 1, 3, and 4.

🧠 Conceptual

intermediate

Key Idea Behind Activity Selection Problem

Which of the following best describes the main idea behind the greedy solution to the Activity Selection Problem?

A Always pick the activity that starts latest among the remaining activities.

B Always pick the activity with the shortest duration.

C Always pick the activity that finishes earliest among the remaining activities.

D Always pick the activity with the earliest start time.

💡 Hint

Think about how to leave room for as many activities as possible.

The greedy approach picks the activity that finishes earliest to maximize the remaining time for other activities.

🔧 Debug

advanced

Identify the Bug in Activity Selection Implementation

What is the bug in this Go code snippet for the Activity Selection Problem?

DSA Go

func activitySelection(start []int, end []int) []int {
    n := len(start)
    selected := []int{0}
    lastEnd := end[0]
    for i := 1; i < n; i++ {
        if start[i] > lastEnd {
            selected = append(selected, i)
            lastEnd = end[i]
        }
    }
    return selected
}

A The initial selected slice should be empty, not contain 0.

B The condition should be start[i] >= lastEnd instead of start[i] > lastEnd.

C The loop should start from i = 0, not i = 1.

D The end array should be sorted before the loop.

💡 Hint

Check the condition that allows selecting an activity starting exactly when the last one ends.

Using '>' excludes activities that start exactly when the previous one ends, which is allowed. The condition must be '>='.

🚀 Application

advanced

Maximum Number of Activities Selected

Given the start times [2, 1, 3, 0, 5, 8, 5] and end times [3, 2, 4, 6, 7, 9, 9], how many activities can be selected without overlapping?

A 5

B 3

C 4

D 6

💡 Hint

Sort activities by their finish times and select greedily.

After sorting by end times, the selected activities are indices 1, 0, 2, 4, and 5, totaling 5.

📝 Syntax

expert

Syntax Error in Activity Selection Go Code

Which option contains a syntax error in this Go code snippet for activity selection?

DSA Go

func activitySelection(start []int, end []int) []int {
    n := len(start)
    selected := []int{0}
    lastEnd := end[0]
    for i := 1; i < n; i++ {
        if start[i] >= lastEnd {
            selected = append(selected, i)
            lastEnd = end[i]
        }
    }
    return selected
}

A func activitySelection(start []int, end []int) []int { n := len(start) selected := []int{0} lastEnd := end[0] for i := 1; i < n; i++ { if start[i] >= lastEnd { selected = append(selected, i) lastEnd = end[i] } return selected } }

B } detceles nruter } } ]i[dne = dnEtsal )i ,detceles(dneppa = detceles { dnEtsal => ]i[trats fi { ++i ;n < i ;1 =: i rof ]0[dne =: dnEtsal }0{tni][ =: detceles )trats(nel =: n { tni][ )tni][ dne ,tni][ trats(noitceleSytivitca cnuf

C func activitySelection(start []int, end []int) []int { n := len(start) selected := []int{0} lastEnd := end[0] for i := 1; i < n; i++ { if start[i] >= lastEnd { selected = append(selected, i) lastEnd = end[i] } } return selected }

D unc activitySelection(start []int, end []int) []int { n := len(start) selected := []int{0} lastEnd := end[0] for i := 1; i < n; i++ { if start[i] >= lastEnd { selected = append(selected, i) lastEnd = end[i] } } return selected }

💡 Hint

Check the placement of the return statement inside the loop.

Option A returns inside the loop, causing a syntax error or premature return.

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