Activity Selection Problem in DSA Java

Mental Model

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

Analogy: Imagine you have a single meeting room and many meetings to schedule. To fit the most meetings, you always pick the one that ends soonest, so you free the room quickly for the next meeting.

Activities with start and end times:
[1, 4] -> [3, 5] -> [0, 6] -> [5, 7] -> [8, 9] -> [5, 9]
We want to select non-overlapping activities like:
[1, 4] -> [5, 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

Step 1: Sort activities by their finish time

[1,4] -> [3,5] -> [0,6] -> [5,7] -> [8,9] -> [5,9]

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

Step 2: Select first activity [1,4]

[1,4] (selected)

Why: First activity always selected as it finishes earliest

Step 3: Check next activity [3,5], start 3 < last finish 4, skip

[1,4] (selected)

Why: Overlaps with last selected activity, so skip

Step 4: Check next activity [0,6], start 0 < last finish 4, skip

[1,4] (selected)

Why: Overlaps with last selected activity, so skip

Step 5: Check next activity [5,7], start 5 ≥ last finish 4, select

[1,4] -> [5,7] (selected)

Why: No overlap, so select this activity

Step 6: Check next activity [8,9], start 8 ≥ last finish 7, select

[1,4] -> [5,7] -> [8,9] (selected)

Why: No overlap, select this activity

Step 7: Check next activity [5,9], start 5 < last finish 9, skip

[1,4] -> [5,7] -> [8,9] (selected)

Why: Overlaps with last selected activity, skip

Result:

[1,4] -> [5,7] -> [8,9] (selected) -- maximum activities without overlap

Annotated Code

DSA Java

import java.util.*;

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

public class ActivitySelection {
    // Function to select maximum activities
    public static List<Activity> selectActivities(Activity[] activities) {
        if (activities == null || activities.length == 0) {
            return new ArrayList<>();
        }
        // Sort activities by finish time
        Arrays.sort(activities, Comparator.comparingInt(a -> a.finish));

        List<Activity> selected = new ArrayList<>();
        // Select first activity
        selected.add(activities[0]);
        int lastFinish = activities[0].finish;

        // Iterate over remaining activities
        for (int i = 1; i < activities.length; i++) {
            // If start time is after or equal to last finish, select
            if (activities[i].start >= lastFinish) {
                selected.add(activities[i]);
                lastFinish = activities[i].finish;
            }
        }
        return selected;
    }

    public static void main(String[] args) {
        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)
        };

        List<Activity> result = selectActivities(activities);
        for (Activity a : result) {
            System.out.print("[" + a.start + "," + a.finish + "] ");
        }
        System.out.println();
    }
}

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

Sort activities by their finish time to prioritize earliest finishing

selected.add(activities[0]);

Select the first activity as starting point

if (activities[i].start >= lastFinish) {

Check if current activity starts after last selected activity finishes

selected.add(activities[i]);

Add current activity to selected list if no overlap

lastFinish = activities[i].finish;

Update last finish time to current activity's finish

Output

[1,4] [5,7] [8,9] 

Complexity Analysis

Time: O(n log n) because we sort the activities by finish time, then traverse once

Space: O(n) for storing the selected activities list

vs Alternative: Naive approach tries all subsets with exponential time; greedy sorting reduces to O(n log n)

Edge Cases

Empty activity list

Returns empty list instead of throwing exception

DSA Java

if (activities == null || activities.length == 0) { return new ArrayList<>(); }

All activities overlap

Only one activity (the earliest finishing) is selected

DSA Java

if (activities[i].start >= lastFinish) {

Activities with same finish time

Selects the first one encountered, others skipped if overlapping

DSA Java

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

When to Use This Pattern

When asked to schedule maximum non-overlapping intervals or tasks, use the greedy approach of sorting by finish time and selecting earliest finishing activities first.

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 by checking only start times without updating last finish
Fix: Update lastFinish after selecting an activity to correctly check overlaps

Summary

Selects the maximum number of non-overlapping activities by always choosing the earliest finishing one.

Use when you need to schedule the most tasks or events without conflicts.

The key insight is sorting by finish time to greedily pick activities that free up time earliest.

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