Activity Selection Problem in DSA Java - Deep Dive

Overview - Activity Selection Problem

What is it?

The Activity Selection Problem is about choosing the maximum number of activities that don't overlap in time from a list of activities, each with a start and end time. The goal is to attend as many activities as possible without any two happening at the same time. This problem helps us understand how to make the best choices when resources like time are limited. It is a classic example of a greedy algorithm in action.

Why it matters

Without this concept, we might waste time trying to attend overlapping activities or make poor scheduling decisions. It helps in real life when planning meetings, events, or tasks to maximize productivity. The problem teaches how to pick the best options step-by-step, which is useful in many scheduling and resource allocation situations.

Where it fits

Before learning this, you should understand arrays, sorting, and basic algorithm concepts like loops and conditions. After this, you can explore other greedy algorithms, dynamic programming, and more complex scheduling problems.

Mental Model

Core Idea

Pick the earliest finishing activity first to leave room for more activities later.

Think of it like...

Imagine you have a single meeting room and many people want to use it. To fit the most meetings, you always let the meeting that ends soonest go first, so the room becomes free quickly for others.

Activities sorted by finish time:
┌───────────────┐
│ Activity List │
├───────────────┤
│ A1: 1 - 4    │
│ A2: 3 - 5    │
│ A3: 0 - 6    │
│ A4: 5 - 7    │
│ A5: 8 - 9    │
└───────────────┘

Selection process:
Start with A1 (ends at 4)
Skip A2 (starts at 3, overlaps)
Skip A3 (starts at 0, overlaps)
Pick A4 (starts at 5, after 4)
Pick A5 (starts at 8, after 7)

Result: A1 -> A4 -> A5

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Learn what the activity selection problem is and how activities are represented.

Activities are given as pairs of start and end times. For example, an activity might start at 1 and end at 4. The problem is to select the maximum number of activities that do not overlap in time.

Result

You understand that overlapping means two activities share some time, so you cannot do both.

Understanding the problem setup is crucial because it defines what counts as a valid selection and what does not.

2

Foundation

Sorting Activities by Finish Time

Concept: Sort activities by their finishing times to prepare for greedy selection.

Given a list of activities, sort them so the one that finishes earliest comes first. For example, activities [(1,4), (3,5), (0,6)] become [(1,4), (3,5), (0,6)] sorted by finish time 4,5,6.

Result

Activities are ordered to help pick the earliest finishing activity first.

Sorting by finish time sets the stage for the greedy choice, ensuring we always pick the activity that frees up time earliest.

3

Intermediate

Greedy Selection Algorithm

🤔Before reading on: do you think picking the longest activity first or the earliest finishing activity first leads to more total activities? Commit to your answer.

Concept: Select activities by always choosing the next activity that starts after the last selected one finishes.

Start by selecting the first activity in the sorted list. Then, for each next activity, check if its start time is after or equal to the finish time of the last selected activity. If yes, select it; if no, skip it.

Result

You get a list of activities that do not overlap and is as large as possible.

Knowing to pick the earliest finishing activity first ensures maximum room for future activities, which is the core greedy strategy.

4

Intermediate

Implementing in Java with Arrays

Concept: Translate the greedy algorithm into Java code using arrays for start and finish times.

Use two arrays: start[] and finish[]. Sort activities by finish[]. Then iterate, selecting activities where start[i] >= finish[last_selected]. Store selected indices or print them.

Result

Java code that outputs the maximum set of non-overlapping activities.

Implementing the algorithm concretely helps solidify the abstract greedy idea into practical coding skills.

5

Intermediate

Dry Run with Sample Data

🤔Before reading on: predict which activities will be selected from [(1,4), (3,5), (0,6), (5,7), (8,9)]. Commit to your answer.

Concept: Walk through the algorithm step-by-step with example activities to see how selection happens.

Sort by finish time: (1,4), (3,5), (0,6), (5,7), (8,9) Select (1,4) Skip (3,5) because it starts before 4 Skip (0,6) because it starts before 4 Select (5,7) because it starts after 4 Select (8,9) because it starts after 7

Result

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

Dry runs reveal how the greedy choice leads to the optimal solution and build confidence in the algorithm.

6

Advanced

Handling Edge Cases and Equal Finish Times

🤔Before reading on: do you think activities with the same finish time can both be selected? Commit to yes or no.

Concept: Understand how to handle activities that finish at the same time and other tricky cases.

If two activities finish at the same time, selecting the one that starts earlier or later can affect the solution. The standard approach is to sort by finish time and pick the first one encountered. Also, activities with zero length or overlapping start and finish times need careful handling.

Result

Algorithm correctly handles ties and edge cases without breaking.

Knowing how to handle edge cases prevents bugs and ensures the algorithm works in all scenarios.

7

Expert

Greedy Algorithm Optimality Proof

🤔Before reading on: do you think the greedy approach always finds the maximum number of activities? Commit to yes or no.

Concept: Understand why the greedy choice of earliest finishing activity leads to an optimal solution.

The proof shows that picking the earliest finishing activity leaves the most room for remaining activities. If an optimal solution did not pick the earliest finishing activity, it can be transformed to one that does without losing the number of activities selected.

Result

You understand the theoretical guarantee behind the greedy algorithm's correctness.

Understanding the proof builds trust in the algorithm and prepares you for more complex greedy problems.

Under the Hood

The algorithm works by sorting activities by their finish times, then iterating through them once, selecting activities that start after the last selected activity ends. This single pass ensures O(n log n) time due to sorting, with O(n) selection. Internally, it uses comparisons and simple checks to maintain the current end time and decide on selection.

Why designed this way?

The problem was designed to model scheduling conflicts simply. Sorting by finish time was chosen because it guarantees the earliest freeing of resources, which is a natural greedy choice. Alternatives like sorting by start time or duration do not guarantee optimal solutions, so this design balances simplicity and correctness.

┌───────────────┐
│ Input:        │
│ Activities[]  │
├───────────────┤
│ Sort by finish│
│ time          │
├───────────────┤
│ Iterate list: │
│ For each act  │
│ if start >=   │
│ last_finish:  │
│ select it     │
├───────────────┤
│ Output:       │
│ Max activities│
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does picking the longest activity first maximize the number of activities? Commit to yes or no.

Common Belief: Choosing the longest activity first will maximize the total time used and thus the number of activities.

Reality: Picking the longest activity first often reduces the total number of activities because it blocks more time, leaving less room for others.

Why it matters: Choosing longest first can lead to fewer activities attended, which defeats the problem's goal.

Quick: Can sorting activities by start time alone solve the problem optimally? Commit to yes or no.

Common Belief: Sorting by start time and picking activities in that order will give the best schedule.

Reality: Sorting by start time does not guarantee the maximum number of non-overlapping activities; sorting by finish time is necessary.

Why it matters: Using start time sorting can cause suboptimal schedules and missed opportunities.

Quick: Is it always possible to select all activities if they have different start and end times? Commit to yes or no.

Common Belief: If activities have different times, you can always select all of them without overlap.

Reality: Many activities overlap in time, so selecting all is usually impossible; the problem is about choosing the best subset.

Why it matters: Assuming all can be selected leads to ignoring conflicts and wrong solutions.

Expert Zone

1

The greedy choice property depends critically on sorting by finish time, not start time or duration.

2

In some variants, activities may have weights or values, requiring dynamic programming instead of greedy.

3

Tie-breaking in sorting can affect which optimal solution is found but not the maximum count.

When NOT to use

When activities have different values or priorities, or when partial overlaps are allowed, greedy selection fails. Instead, use weighted interval scheduling with dynamic programming or interval trees.

Production Patterns

Used in calendar apps to suggest free time slots, in CPU scheduling to maximize throughput, and in event planning software to optimize room usage.

Connections

Greedy Algorithms

The activity selection problem is a classic example of a greedy algorithm.

Understanding this problem helps grasp the greedy approach of making locally optimal choices to achieve a global optimum.

Interval Scheduling

Activity selection is a specific case of interval scheduling problems.

Knowing activity selection aids in understanding more complex interval scheduling variants with weights or resources.

Resource Allocation in Operations Research

Activity selection models how to allocate limited resources (time slots) efficiently.

This connection shows how computer algorithms solve real-world scheduling and resource management problems.

Common Pitfalls

#1 Selecting activities without sorting by finish time.

Wrong approach:

for (int i = 0; i < n; i++) {
if (start[i] >= lastFinish) {
select activity i;
lastFinish = finish[i];
}
} // but start and finish arrays are unsorted

Correct approach:

Sort activities by finish time first, then:
for (int i = 0; i < n; i++) {
if (start[i] >= lastFinish) {
select activity i;
lastFinish = finish[i];
}
}

Root cause:

Not sorting breaks the greedy strategy, causing wrong selections and suboptimal results.

#2 Comparing start time with the start time of the last selected activity instead of finish time.

Wrong approach:

if (start[i] >= start[lastSelected]) { select activity i; }

Correct approach:

if (start[i] >= finish[lastSelected]) { select activity i; }

Root cause:

Confusing start and finish times leads to overlapping activities being selected.

#3 Assuming activities with equal finish times can both be selected.

Wrong approach:

Select all activities where start[i] >= finish[lastSelected], even if finish times are equal and overlap.

Correct approach:

Select only activities where start[i] >= finish[lastSelected], ensuring no overlap even if finish times are equal.

Root cause:

Misunderstanding that equal finish times can still cause overlap if start times are not strictly after finish.

Key Takeaways

The Activity Selection Problem teaches how to maximize non-overlapping activities by always choosing the earliest finishing activity first.

Sorting activities by their finish times is essential to apply the greedy algorithm correctly.

Greedy algorithms work here because the earliest finishing activity leaves the most room for others, guaranteeing an optimal solution.

Edge cases like equal finish times and overlapping intervals require careful handling to avoid mistakes.

Understanding this problem builds a foundation for more complex scheduling and resource allocation challenges.

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