Activity Selection Problem in DSA Java - 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 Java

int[] start = {1, 3, 0, 5, 8, 5};
int[] finish = {2, 4, 6, 7, 9, 9};
selectActivities(start, finish);

Select maximum number of activities that don't overlap from given start and finish times.

Execution Table

Step	Operation	Selected Activities	Current Activity (start, finish)	Condition (start >= last finish?)	Action	Visual State
1	Sort activities by finish time	[]	[(1,2),(3,4),(0,6),(5,7),(8,9),(5,9)]	-	Sorted activities	(1,2),(3,4),(0,6),(5,7),(8,9),(5,9)
2	Select first activity	[(1,2)]	(3,4)	-	Select (1,2)	(1,2)
3	Check next activity	[(1,2)]	(3,4)	3 >= 2? Yes	Select (3,4)	(1,2) -> (3,4)
4	Check next activity	[(1,2),(3,4)]	(0,6)	0 >= 4? No	Skip (0,6)	(1,2) -> (3,4)
5	Check next activity	[(1,2),(3,4)]	(5,7)	5 >= 4? Yes	Select (5,7)	(1,2) -> (3,4) -> (5,7)
6	Check next activity	[(1,2),(3,4),(5,7)]	(8,9)	8 >= 7? Yes	Select (8,9)	(1,2) -> (3,4) -> (5,7) -> (8,9)
7	Check next activity	[(1,2),(3,4),(5,7),(8,9)]	(5,9)	5 >= 9? No	Skip (5,9)	(1,2) -> (3,4) -> (5,7) -> (8,9)
8	All activities checked	[(1,2),(3,4),(5,7),(8,9)]	-	-	Done	(1,2) -> (3,4) -> (5,7) -> (8,9)

💡 All activities checked, no more to select

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
selectedActivities	[]	[(1,2)]	[(1,2),(3,4)]	[(1,2),(3,4)]	[(1,2),(3,4),(5,7)]	[(1,2),(3,4),(5,7),(8,9)]	[(1,2),(3,4),(5,7),(8,9)]	[(1,2),(3,4),(5,7),(8,9)]
lastFinishTime	-	2	4	4	7	9	9	9
currentActivity	-	(3,4)	(0,6)	(5,7)	(8,9)	(5,9)	-	-

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 Step 1 in execution_table where sorting happens.

Why do we compare current activity's start time with last selected finish time?

To avoid overlapping activities, we only select an activity if it starts after or exactly when the last selected one finishes. This is shown in Steps 3-7 in execution_table under the condition column.

What happens if an activity starts before the last selected activity finishes?

We skip that activity to prevent overlap, as shown in Steps 4 and 7 where the condition is false and action is to skip.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the selectedActivities list?

A [(1,2),(3,4),(5,7)]

B [(1,2),(3,4)]

C [(1,2),(3,4),(0,6)]

D [(1,2),(3,4),(5,9)]

💡 Hint

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

At which step does the condition 'start >= last finish' become false for the first time?

A Step 3

B Step 6

C Step 4

D Step 7

💡 Hint

Look at the 'Condition' and 'Action' columns in execution_table rows.

If the activity (5,9) had finish time 8 instead of 9, how would the final selectedActivities change?

A It would still be skipped

B It would be selected, adding to the list

C It would replace (8,9)

D It would be selected before (5,7)

💡 Hint

Compare the condition 'start >= last finish' for (5,9) with finish time 8 instead of 9.

Concept Snapshot

Activity Selection Problem:
- Sort activities by finish time
- Select first activity
- For each next activity, select if start >= last selected finish
- Skip otherwise
- 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, starting with the first activity, each next activity is checked. 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 list contains the maximum set of compatible activities.

Practice

1. What is the main goal of the Activity Selection Problem?

easy

A. Calculate the total time of all activities

B. Find the activity with the longest duration

C. Sort activities by their start time

D. Select the maximum number of activities that don't overlap

Solution

1. Step 1: Understand the problem objective

   The Activity Selection Problem aims to choose the largest set of activities that do not overlap in time.

2. Step 2: Identify the correct goal

   Among the options, only selecting the maximum number of non-overlapping activities matches the problem's goal.

3. Final Answer:

   Select the maximum number of activities that don't overlap -> Option D

4. Quick Check:

   Goal = Max non-overlapping activities [OK]

Hint: Focus on maximizing non-overlapping activities [OK]

Common Mistakes:

• Confusing longest duration with maximum count
• Sorting by start time only
• Summing all activity durations

2. Which of the following Java code snippets correctly sorts activities by their finish time for the Activity Selection Problem?

easy

A. Arrays.sort(activities, (a, b) -> a.finish - b.finish);

B. Arrays.sort(activities, (a, b) -> a.start - b.start);

C. Arrays.sort(activities, (a, b) -> b.finish - a.finish);

D. Arrays.sort(activities, (a, b) -> b.start - a.start);

Solution

1. Step 1: Identify sorting criteria for Activity Selection

   Activities must be sorted by their finish time in ascending order to apply the greedy approach.

2. Step 2: Match code to sorting by finish time ascending

   Arrays.sort(activities, (a, b) -> a.finish - b.finish); sorts by finish time ascending (a.finish - b.finish), which is correct.

3. Final Answer:

   Arrays.sort(activities, (a, b) -> a.finish - b.finish); -> Option A

4. Quick Check:

   Sort by finish time ascending = Arrays.sort(activities, (a, b) -> a.finish - b.finish); [OK]

Hint: Sort activities by finish time ascending [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Sorting in descending order
• Using incorrect comparator syntax

3. What is the output of the following Java code snippet for the Activity Selection Problem?

class Activity {
  int start, finish;
  Activity(int s, int f) { start = s; finish = f; }
}

Activity[] activities = {
  new Activity(1, 4),
  new Activity(3, 5),
  new Activity(0, 6),
  new Activity(5, 7),
  new Activity(8, 9),
  new Activity(5, 9)
};

Arrays.sort(activities, (a, b) -> a.finish - b.finish);

int count = 1;
int lastFinish = activities[0].finish;
for (int i = 1; i < activities.length; i++) {
  if (activities[i].start >= lastFinish) {
    count++;
    lastFinish = activities[i].finish;
  }
}
System.out.println(count);

medium

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Sort activities by finish time ascending

   The activities in sorted order (stable sort preserves order of ties): (1,4), (3,5), (0,6), (5,7), (8,9), (5,9)

2. Step 2: Trace the greedy selection

   Pick (1,4), count=1, lastFinish=4
   Skip (3,5) since 3 < 4
   Skip (0,6) since 0 < 4
   Pick (5,7) since 5 >= 4, count=2, lastFinish=7
   Pick (8,9) since 8 >= 7, count=3, lastFinish=9
   Skip (5,9) since 5 < 9

3. Step 3: Check if any other activities can be selected

   All activities considered, total count = 4 (including the first selected activity)

4. Final Answer:

   4 -> Option C

5. Quick Check:

   Greedy selection count = 4 [OK]

Hint: Sort by finish time, pick next starting after last finish [OK]

Common Mistakes:

• Not sorting activities before selection
• Selecting overlapping activities
• Incorrectly updating last finish time

4. Identify the error in the following Java code snippet for the Activity Selection Problem:

Arrays.sort(activities, (a, b) -> a.finish + b.finish);

int count = 1;
int lastFinish = activities[0].finish;
for (int i = 1; i < activities.length; i++) {
  if (activities[i].start >= lastFinish) {
    count++;
    lastFinish = activities[i].finish;
  }
}
System.out.println(count);

medium

A. Loop starts from index 0 instead of 1

B. Comparator uses addition instead of subtraction for sorting

C. Condition should check start > lastFinish, not >= lastFinish

D. Count variable is not initialized

Solution

1. Step 1: Analyze the comparator in Arrays.sort

   The comparator uses a.finish + b.finish, which does not correctly compare finish times. It should use subtraction (a.finish - b.finish) to sort ascending.

2. Step 2: Understand impact of incorrect comparator

   Using addition returns a positive number regardless of order, causing incorrect sorting and wrong activity selection.

3. Final Answer:

   Comparator uses addition instead of subtraction for sorting -> Option B

4. Quick Check:

   Comparator must subtract finish times [OK]

Hint: Use subtraction in comparator, not addition [OK]

Common Mistakes:

• Using addition in comparator instead of subtraction
• Starting loop at wrong index
• Misunderstanding condition operator

5. Given the following activities with start and finish times:

int[] start = {1, 3, 0, 5, 8, 5};
int[] finish = {2, 4, 6, 7, 9, 9};

Which set of activities selected by the greedy algorithm (selecting earliest finish time first) is correct?

hard

A. [Activity(1,2), Activity(3,4), Activity(5,7), Activity(8,9)]

B. [Activity(0,6), Activity(5,7), Activity(8,9)]

C. [Activity(1,2), Activity(5,9)]

D. [Activity(3,4), Activity(5,7), Activity(5,9)]

Solution

1. Step 1: Sort activities by finish time ascending

   Activities sorted by finish time:
   (1,2), (3,4), (0,6), (5,7), (8,9), (5,9)

2. Step 2: Select activities greedily

   Pick (1,2) first.
   Next, (3,4) start=3 >=2 select.
   (0,6) start=0 <4 skip.
   (5,7) start=5 >=4 select.
   (8,9) start=8 >=7 select.
   (5,9) start=5 <7 skip.

3. Step 3: Final selected set

   [Activity(1,2), Activity(3,4), Activity(5,7), Activity(8,9)]

4. Final Answer:

   [Activity(1,2), Activity(3,4), Activity(5,7), Activity(8,9)] -> Option A

5. Quick Check:

   Greedy selection = [Activity(1,2), Activity(3,4), Activity(5,7), Activity(8,9)] [OK]

Hint: Pick activities with earliest finish time, skip overlapping [OK]

Common Mistakes:

• Choosing activities with longer duration
• Selecting overlapping activities
• Ignoring sorting by finish time