Activity Selection Problem in DSA Javascript - Build from Scratch

Activity Selection Problem

📖 Scenario: You are organizing a conference with many talks. Each talk has a start time and an end time. You want to attend the maximum number of talks without any overlaps.

🎯 Goal: Build a program that selects the maximum number of non-overlapping activities (talks) you can attend.

📋 What You'll Learn

Create an array of activities with exact start and end times

Add a variable to store the number of activities

Sort activities by their end time

Select the maximum number of non-overlapping activities

Print the selected activities in order

💡 Why This Matters

🌍 Real World

Scheduling talks, meetings, or tasks without overlap to maximize usage of time.

💼 Career

Useful for roles in project management, event planning, and software engineering where resource allocation and scheduling are important.

1

Create the activities array

Create an array called activities with these exact objects: {start: 1, end: 4}, {start: 3, end: 5}, {start: 0, end: 6}, {start: 5, end: 7}, {start: 8, end: 9}, {start: 5, end: 9}

DSA Javascript

// Your code here

Hint

Use an array of objects with start and end properties.

2

Add the number of activities variable

Create a variable called n and set it to the length of the activities array

DSA Javascript

const activities = [
  {start: 1, end: 4},
  {start: 3, end: 5},
  {start: 0, end: 6},
  {start: 5, end: 7},
  {start: 8, end: 9},
  {start: 5, end: 9}
];
// Your code here

Hint

Use activities.length to get the number of activities.

3

Sort activities by end time and select maximum activities

Sort the activities array by the end property in ascending order. Then create an array called selectedActivities and add the first activity from the sorted array. Use a for loop with variable i from 1 to n - 1 to check if the current activity's start time is greater or equal to the last selected activity's end time. If yes, add the current activity to selectedActivities

DSA Javascript

const activities = [
  {start: 1, end: 4},
  {start: 3, end: 5},
  {start: 0, end: 6},
  {start: 5, end: 7},
  {start: 8, end: 9},
  {start: 5, end: 9}
];
const n = activities.length;
// Your code here

Hint

Sort by end time, then pick activities that start after the last selected one ends.

4

Print the selected activities

Use a for loop with variable activity to iterate over selectedActivities and print each activity's start and end times in the format start - end

DSA Javascript

const activities = [
  {start: 1, end: 4},
  {start: 3, end: 5},
  {start: 0, end: 6},
  {start: 5, end: 7},
  {start: 8, end: 9},
  {start: 5, end: 9}
];
const n = activities.length;
activities.sort((a, b) => a.end - b.end);
const selectedActivities = [activities[0]];
for (let i = 1; i = selectedActivities[selectedActivities.length - 1].end) {
    selectedActivities.push(activities[i]);
  }
}
// Your code here

Hint

Print each selected activity's start and end times separated by ' - ' on its own line.

Practice

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

easy

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

B. Find the activity with the longest duration

C. Sort activities by their start times

D. Calculate the total time of all activities

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Clarify what is NOT the goal

   Finding the longest activity or sorting alone does not solve the problem; the focus is on maximizing non-overlapping activities.

3. Final Answer:

   Select the maximum number of activities that don't overlap in time -> Option A

4. Quick Check:

   Maximize non-overlapping activities = Select max activities [OK]

Hint: Focus on non-overlapping activities to maximize count [OK]

Common Mistakes:

• Thinking it's about longest activity duration
• Confusing sorting with selection
• Trying to maximize total time instead of count

2. Which of the following is the correct way to sort activities by their finish time in JavaScript?

easy

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

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

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

D. activities.sort((a, b) => a.duration - b.duration);

Solution

1. Step 1: Identify sorting key for Activity Selection

   We must sort activities by their finish time in ascending order to apply the greedy approach.

2. Step 2: Choose correct JavaScript sort syntax

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

3. Final Answer:

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

4. Quick Check:

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

Hint: Sort activities by finish time ascending for greedy selection [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Sorting finish time descending
• Sorting by duration which is irrelevant here

3. What will be the output of the following code snippet?

const activities = [
  {start: 1, finish: 4},
  {start: 3, finish: 5},
  {start: 0, finish: 6},
  {start: 5, finish: 7},
  {start: 8, finish: 9},
  {start: 5, finish: 9}
];

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

let count = 1;
let lastFinish = activities[0].finish;

for (let i = 1; i < activities.length; i++) {
  if (activities[i].start >= lastFinish) {
    count++;
    lastFinish = activities[i].finish;
  }
}
console.log(count);

medium

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Sort activities by finish time

   Sorted activities by finish time ascending: [{start:1, finish:4}, {start:3, finish:5}, {start:0, finish:6}, {start:5, finish:7}, {start:8, finish:9}, {start:5, finish:9}].

2. Step 2: Select activities greedily

   Start with first activity (finish=4). Next, select activities starting >=4: (start=5, finish=7), count=2; then (start=8, finish=9), count=3; then (start=9, finish=9) does not exist but next is (start=5, finish=9) which starts before 9, so skip. Total count is 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Greedy selection count = 4 [OK]

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

Common Mistakes:

• Not sorting activities before selection
• Counting overlapping activities
• Updating lastFinish incorrectly

4. Identify the bug in the following code for Activity Selection Problem:

function selectActivities(activities) {
  activities.sort((a, b) => a.start - b.start);
  let count = 1;
  let lastFinish = activities[0].finish;
  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start > lastFinish) {
      count++;
      lastFinish = activities[i].finish;
    }
  }
  return count;
}

medium

A. Initialize count to 0 instead of 1

B. Comparison should be activities[i].start >= lastFinish

C. Sorting should be by finish time, not start time

D. No bug, code is correct

Solution

1. Step 1: Check sorting criteria

   The greedy approach requires sorting activities by their finish time, but the code sorts by start time, which is incorrect.

2. Step 2: Understand impact of wrong sorting

   Sorting by start time can cause wrong selection order, leading to suboptimal count of activities.

3. Final Answer:

   Sorting should be by finish time, not start time -> Option C

4. Quick Check:

   Sort by finish time for correct greedy selection [OK]

Hint: Always sort by finish time, not start time [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Using > instead of >= in condition (less critical)
• Incorrect initialization of count

5. Given the activities with start and finish times:

const activities = [
  {start: 2, finish: 3},
  {start: 1, finish: 4},
  {start: 5, finish: 7},
  {start: 6, finish: 9},
  {start: 8, finish: 10},
  {start: 9, finish: 11}
];

What is the maximum number of non-overlapping activities that can be selected?

hard

A. 6

B. 4

C. 5

D. 3

Solution

1. Step 1: Sort activities by finish time

   Sorted activities by finish time ascending: [{start:2, finish:3}, {start:1, finish:4}, {start:5, finish:7}, {start:6, finish:9}, {start:8, finish:10}, {start:9, finish:11}].

2. Step 2: Select activities greedily

   Select (2,3), then (5,7), then (8,10), then (9,11) overlaps with (8,10) so skip; but (6,9) overlaps with (5,7) so skip. Total count is 4.

3. Step 3: Check for more selections

   Others overlap and cannot be selected without violating non-overlap. Maximum count is 4.

4. Final Answer:

   4 -> Option B

5. Quick Check:

   Max non-overlapping activities = 4 [OK]

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

Common Mistakes:

• Not sorting activities before selection
• Selecting overlapping activities
• Ignoring start time conditions