Job Scheduling with Deadlines in DSA Typescript - Time & Space Complexity

Time Complexity: Job Scheduling with Deadlines

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to schedule jobs grows as the number of jobs increases.

How does the code handle more jobs and deadlines efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function jobScheduling(jobs: {id: number, deadline: number, profit: number}[]): number[] {
  jobs.sort((a, b) => b.profit - a.profit);
  const result: number[] = [];
  const slot: boolean[] = Array(jobs.length).fill(false);
  for (const job of jobs) {
    for (let j = Math.min(jobs.length, job.deadline) - 1; j >= 0; j--) {
      if (!slot[j]) {
        slot[j] = true;
        result.push(job.id);
        break;
      }
    }
  }
  return result;
}
    

This code schedules jobs to maximize profit by placing each job in the latest available slot before its deadline.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where the outer loop goes through each job and the inner loop searches for a free slot before the job's deadline.
• How many times: Outer loop runs once per job (n times), inner loop can run up to n times in worst case.

How Execution Grows With Input

As the number of jobs grows, the code checks more jobs and searches more slots for each job.

Input Size (n)	Approx. Operations
10	Up to 100 checks (10 jobs x 10 slots)
100	Up to 10,000 checks (100 jobs x 100 slots)
1000	Up to 1,000,000 checks (1000 jobs x 1000 slots)

Pattern observation: The number of operations grows roughly with the square of the number of jobs.

Final Time Complexity

Time Complexity: O(n2)

This means if you double the number of jobs, the time to schedule them roughly quadruples.

Common Mistake

[X] Wrong: "The inner loop only runs once per job, so the code is O(n)."

[OK] Correct: Sometimes the inner loop must check many slots before finding a free one, especially when deadlines overlap, causing many repeated checks.

Interview Connect

Understanding how nested loops affect time helps you explain your approach clearly and shows you can analyze efficiency in real problems.

Self-Check

"What if we used a data structure to find free slots faster? How would the time complexity change?"