Activity Selection Problem in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Activity Selection

What is the output of the following Java code that selects the maximum number of activities that don't overlap?

DSA Java

import java.util.*;
class Activity {
    int start, finish;
    Activity(int s, int f) { start = s; finish = f; }
}
public class Main {
    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)
        };
        Arrays.sort(activities, Comparator.comparingInt(a -> a.finish));
        int count = 1;
        int lastFinish = activities[0].finish;
        StringBuilder selected = new StringBuilder("1");
        for (int i = 1; i < activities.length; i++) {
            if (activities[i].start >= lastFinish) {
                count++;
                lastFinish = activities[i].finish;
                selected.append(" -> ").append(i + 1);
            }
        }
        System.out.println(selected.toString() + " -> null");
    }
}

A 1 -> 2 -> 4 -> 5 -> null

B 1 -> 4 -> 5 -> null

C 1 -> 4 -> 6 -> null

D 1 -> 3 -> 5 -> null

💡 Hint

Look at activities sorted by finish time and pick those starting after the last selected finish.

The code sorts activities by their finish time. It picks the first activity (index 0). Then it selects the next activity whose start time is >= last selected finish time. The selected activities are 1 (index 0), 4 (index 3), and 5 (index 4).

🧠 Conceptual

intermediate

Key Idea Behind Activity Selection Problem

What is the main idea behind the greedy solution to the Activity Selection Problem?

A Always pick the activity with the shortest duration first.

B Always pick the activity with the earliest start time first.

C Always pick the activity that finishes earliest and is compatible with previously selected activities.

D Pick activities randomly and check if they overlap.

💡 Hint

Think about how to maximize the number of activities without overlap.

The greedy approach picks the activity that finishes earliest to leave room for more activities later. This ensures the maximum number of non-overlapping activities.

🔧 Debug

advanced

Identify the Bug in Activity Selection Code

What error will this Java code produce when run?

DSA Java

import java.util.*;
class Activity {
    int start, finish;
    Activity(int s, int f) { start = s; finish = f; }
}
public class Main {
    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 4), new Activity(3, 5), new Activity(0, 6)
        };
        Arrays.sort(activities, (a, b) -> a.start - b.finish);
        System.out.println("Sorted activities");
    }
}

A Compilation error due to lambda syntax

B No error, sorts by finish time correctly

C No error, sorts by start time correctly

D Runtime error due to invalid comparator logic

💡 Hint

Check the comparator logic carefully.

The comparator subtracts a.start - b.finish which mixes start and finish times incorrectly. This can cause inconsistent ordering and runtime exceptions.

🚀 Application

advanced

Maximum Number of Activities Selected

Given activities with start and finish times: (1,3), (2,5), (4,7), (6,9), (8,10), what is the maximum number of non-overlapping activities that can be selected?

A 3

B 5

C 2

D 4

💡 Hint

Sort by finish time and pick compatible activities greedily.

Sorted by finish time: (1,3), (2,5), (4,7), (6,9), (8,10). Select (1,3), then (4,7), then (8,10). Maximum is 3.

❓ Predict Output

expert

Output of Recursive Activity Selection

What is the output of this recursive Java code that prints selected activities indices?

DSA Java

import java.util.*;
class Activity {
    int start, finish;
    Activity(int s, int f) { start = s; finish = f; }
}
public class Main {
    static void recursiveSelect(Activity[] acts, int k, int n) {
        int m = k + 1;
        while (m < n && acts[m].start < acts[k].finish) m++;
        if (m < n) {
            System.out.print((m + 1) + " -> ");
            recursiveSelect(acts, m, n);
        }
    }
    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 2), new Activity(3, 4), new Activity(0, 6),
            new Activity(5, 7), new Activity(8, 9), new Activity(5, 9)
        };
        Arrays.sort(activities, Comparator.comparingInt(a -> a.finish));
        System.out.print("1 -> ");
        recursiveSelect(activities, 0, activities.length);
        System.out.println("null");
    }
}

A 1 -> 2 -> 4 -> 5 -> null

B 1 -> 3 -> 4 -> 6 -> null

C 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

D 1 -> 4 -> 5 -> null

💡 Hint

Trace the recursion picking next compatible activity by start time >= last finish.

The recursive method picks activities by finding the next activity starting after the current one finishes. The selected activities are indices 1, 2, 4, 5 (1-based: 1,2,4,5).

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