Activity Selection Problem in DSA Go - Time & Space Complexity

Time Complexity: Activity Selection Problem

O(n)

Understanding Time Complexity

We want to understand how the time taken by the Activity Selection algorithm changes as the number of activities grows.

Specifically, how does the number of steps grow when we have more activities to choose from?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func ActivitySelection(start, finish []int) []int {
    n := len(start)
    selected := []int{0} // select first activity
    last := 0
    for i := 1; i < n; i++ {
        if start[i] >= finish[last] {
            selected = append(selected, i)
            last = i
        }
    }
    return selected
}
    

This code selects the maximum number of activities that don't overlap, assuming activities are sorted by finish time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that checks each activity once.
• How many times: It runs once for each activity after the first, so n-1 times.

How Execution Grows With Input

As the number of activities increases, the loop runs more times, checking each activity once.

Input Size (n)	Approx. Operations
10	About 9 checks
100	About 99 checks
1000	About 999 checks

Pattern observation: The number of operations grows roughly in a straight line with the number of activities.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows directly in proportion to the number of activities.

Common Mistake

[X] Wrong: "The algorithm checks every pair of activities, so it must be O(n²)."

[OK] Correct: The code only loops once through the activities, not nested loops, so it does not compare every pair.

Interview Connect

Understanding this linear time solution shows you can find efficient answers by careful ordering and simple loops, a skill valued in many coding challenges.

Self-Check

"What if the activities were not sorted by finish time? How would the time complexity change?"

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