Why Activity Selection Problem in DSA Javascript?

The Big Idea

What if you could instantly find the perfect schedule without checking every meeting?

The Scenario

Imagine you have a list of meetings to attend in a day, but some meetings overlap in time. You want to attend as many meetings as possible without any clashes. Trying to pick meetings manually by checking each one against others can get confusing fast.

The Problem

Manually checking every meeting against all others to avoid overlaps is slow and tiring. It's easy to miss a clash or pick fewer meetings than possible. This approach wastes time and can lead to poor scheduling decisions.

The Solution

The Activity Selection Problem uses a smart method to pick the maximum number of non-overlapping meetings. By sorting meetings by their finishing times and always choosing the earliest finishing meeting next, it quickly finds the best schedule without checking every combination.

Before vs After

✗ Before

const meetings = [[1,4],[3,5],[0,6],[5,7]];
// Manually check each meeting against others for overlaps
// Complex and error-prone nested loops

✓ After

const meetings = [[1,4],[3,5],[0,6],[5,7]];
meetings.sort((a,b) => a[1] - b[1]);
// Pick meetings greedily by earliest finish time
// Simple and efficient

What It Enables

This concept enables you to quickly find the largest set of non-overlapping activities, optimizing your schedule effortlessly.

Real Life Example

Scheduling conference talks in different rooms so attendees can attend the most talks without time conflicts.

Key Takeaways

Manual scheduling is slow and error-prone.

Sorting by finish time simplifies selection.

Greedy choice leads to optimal activity selection.

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