Activity Selection Problem in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Activity Selection Problem?

To select the maximum number of activities that don't overlap in time from a given set of activities.

beginner

Which algorithmic approach is commonly used to solve the Activity Selection Problem?

A greedy algorithm that selects the next activity with the earliest finishing time that doesn't conflict with already selected activities.

intermediate

Why do we sort activities by their finishing times in the Activity Selection Problem?

Sorting by finishing times helps to always pick the activity that leaves the most room for others, maximizing the total number of activities selected.

beginner

In the Activity Selection Problem, what condition must be true for an activity to be selected after another?

The start time of the new activity must be greater than or equal to the finish time of the last selected activity.

intermediate

What is the time complexity of the Activity Selection Problem solution using a greedy approach?

O(n log n) due to sorting the activities by their finish times. The selection process itself is O(n).

What is the first step in solving the Activity Selection Problem?

A Sort activities by their durations

B Sort activities by their starting times

C Select activities randomly

D Sort activities by their finishing times

Sorting activities by finishing times ensures the greedy choice picks the earliest finishing activity first.

Which of these best describes the greedy choice in the Activity Selection Problem?

A Pick the activity with the earliest start time

B Pick the activity with the shortest duration

C Pick the activity with the earliest finish time that doesn't overlap

D Pick the activity with the latest finish time

The greedy choice is to pick the earliest finishing activity that is compatible with previously selected activities.

If two activities overlap, what does the Activity Selection Problem algorithm do?

A Select the one with the earlier finish time

B Select the one with the later start time

C Select both activities

D Skip both activities

The algorithm selects the activity that finishes earlier to maximize the number of activities selected.

What data structure is primarily used to store the selected activities in the Activity Selection Problem?

A List or array

B Queue

C Stack

D Tree

A list or array is used to keep track of selected activities in order.

What is the main reason the greedy algorithm works for the Activity Selection Problem?

A Because activities are sorted by start time

B Because the problem has optimal substructure and greedy choice property

C Because it tries all possible combinations

D Because it uses dynamic programming

The problem has optimal substructure and greedy choice property, allowing a greedy algorithm to find the optimal solution.

Explain how the greedy algorithm solves the Activity Selection Problem step-by-step.

Think about sorting and then picking activities that don't overlap.

Why does sorting activities by their finishing times lead to an optimal solution in the Activity Selection Problem?

Consider how choosing the earliest finishing activity affects the rest.