Activity Selection Problem in DSA Go

Mental Model

Choose the most activities that don't overlap by always picking the one that finishes earliest.

Analogy: Imagine you have a single meeting room and many meetings to schedule. To fit the most meetings, always pick the meeting that ends soonest so you can fit more after it.

Activities (start-end times):
[1-4]  [3-5]  [0-6]  [5-7]  [8-9]  [5-9]
Timeline: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

Dry Run Walkthrough

Input: activities: [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)]

Goal: Select the maximum number of activities that don't overlap in time.

Step 1: Sort activities by finish time

[(1,4), (3,5), (0,6), (5,7), (5,9), (8,9)]

Why: Sorting by finish time helps pick the earliest finishing activity first.

Step 2: Select first activity (1,4)

Selected: [(1,4)]

Why: Always pick the first activity after sorting.

Step 3: Check next activity (3,5), overlaps with (1,4), skip

Selected: [(1,4)]

Why: Activity (3,5) starts before (1,4) ends, so it overlaps.

Step 4: Check next activity (0,6), overlaps with (1,4), skip

Selected: [(1,4)]

Why: Activity (0,6) starts before (1,4) ends, so it overlaps.

Step 5: Check next activity (5,7), starts after (1,4) ends, select it

Selected: [(1,4), (5,7)]

Why: No overlap, so we can add this activity.

Step 6: Check next activity (5,9), overlaps with (5,7), skip

Selected: [(1,4), (5,7)]

Why: Starts at same time as (5,7), so overlaps.

Step 7: Check next activity (8,9), starts after (5,7) ends, select it

Selected: [(1,4), (5,7), (8,9)]

Why: No overlap, add this activity.

Result:

Selected activities: (1,4) -> (5,7) -> (8,9) -> null

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

type Activity struct {
	start  int
	finish int
}

// selectActivities returns the maximum set of activities that don't overlap
func selectActivities(activities []Activity) []Activity {
	if len(activities) == 0 {
		return []Activity{}
	}

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

	selected := []Activity{}
	// Always select first activity
	selected = append(selected, activities[0])
	lastFinish := activities[0].finish

	for i := 1; i < len(activities); i++ {
		// If activity starts after or when last selected finishes
		if activities[i].start >= lastFinish {
			selected = append(selected, activities[i])
			lastFinish = activities[i].finish
		}
	}

	return selected
}

func main() {
	activities := []Activity{{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}}
	selected := selectActivities(activities)
	for i, a := range selected {
		fmt.Printf("Activity %d: start=%d, finish=%d\n", i+1, a.start, a.finish)
	}
}

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

sort activities by finish time ascending

selected = append(selected, activities[0])

select first activity after sorting

if activities[i].start >= lastFinish { selected = append(selected, activities[i]); lastFinish = activities[i].finish }

select next activity only if it starts after last selected finishes

Output

Activity 1: start=1, finish=4

Activity 2: start=5, finish=7

Activity 3: start=8, finish=9

Complexity Analysis

Time: O(n log n) because sorting the activities by finish time takes O(n log n), and selecting activities takes O(n)

Space: O(n) because we store the selected activities in a new list

vs Alternative: Naive approach tries all subsets with exponential time; greedy sorting and selecting is efficient and optimal

Edge Cases

empty list of activities

returns empty selection without error

DSA Go

added check for empty activities slice before accessing activities[0]

all activities overlap completely

only one activity is selected, the one finishing earliest

DSA Go

if activities[i].start >= lastFinish { ... } ensures no overlap

activities with same finish time

selects the first one encountered, others skipped if overlapping

DSA Go

sort.Slice sorts by finish time, stable order picks first

When to Use This Pattern

When you need to schedule the maximum number of non-overlapping intervals, use the greedy activity selection pattern by sorting on finish times.

Common Mistakes

Mistake: Sorting activities by start time instead of finish time
Fix: Sort activities by their finish time to ensure earliest finishing activities are chosen first

Mistake: Selecting activities that overlap with previously selected ones
Fix: Check that the next activity starts after or exactly when the last selected activity finishes before selecting

Summary

Selects the maximum number of activities that don't overlap by always picking the earliest finishing activity next.

Use when you want to schedule as many non-overlapping activities as possible from given start and finish times.

The key insight is sorting by finish time lets you greedily pick activities that leave room for more later.

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