Activity Selection Problem in DSA Typescript - Time & Space Complexity

Time Complexity: Activity Selection Problem

O(n)

Understanding Time Complexity

We want to know how the time needed to select activities grows as the number of activities increases.

How does the algorithm's work change when we have more activities to choose from?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function activitySelection(start: number[], finish: number[]): number[] {
  const n = start.length;
  const selected: number[] = [];
  let lastFinish = 0;
  for (let i = 0; i < n; i++) {
    if (start[i] >= lastFinish) {
      selected.push(i);
      lastFinish = finish[i];
    }
  }
  return selected;
}
    

This code picks the maximum number of activities that don't overlap, assuming activities are sorted by finish time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through all activities once.
• How many times: Exactly once for each activity, so n times.

How Execution Grows With Input

As the number of activities grows, the work grows in a straight line.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of operations grows directly with the number of activities.

Final Time Complexity

Time Complexity: O(n)

This means the time to select activities grows in direct proportion to how many activities there are.

Common Mistake

[X] Wrong: "The algorithm checks every pair of activities, so it must be quadratic."

[OK] Correct: The code only loops once through the list, not nested loops, so it does not compare every pair.

Interview Connect

Understanding this linear time solution shows you can spot efficient ways to handle scheduling problems, a useful skill in many coding challenges.

Self-Check

"What if the activities were not sorted by finish time? How would the time complexity change?"