Job Scheduling with Deadlines in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Job Scheduling with Deadlines problem?

To schedule jobs in such a way that the maximum number of jobs are completed before their deadlines, maximizing total profit or count.

beginner

In Job Scheduling with Deadlines, what does each job typically have?

Each job has a deadline by which it must be completed and a profit or value gained if completed on time.

intermediate

Why do we sort jobs by profit in descending order in the greedy approach?

Sorting by profit ensures we try to schedule the most profitable jobs first to maximize total profit.

intermediate

What data structure is commonly used to keep track of free time slots in Job Scheduling with Deadlines?

An array or list representing time slots is used to mark which slots are free or occupied.

intermediate

Explain the greedy step to assign a job to a time slot.

For each job, starting from its deadline slot, check backward to find the latest free slot to schedule it.

What is the first step in the greedy algorithm for Job Scheduling with Deadlines?

A Schedule jobs with earliest deadline first

B Sort jobs by ascending deadline

C Assign jobs randomly

D Sort jobs by descending profit

Sorting jobs by descending profit helps prioritize scheduling the most valuable jobs first.

If a job's deadline is 3, which time slots do we check to schedule it?

A Slots 1 to 3, starting from 3 backwards

B Only slot 3

C Slots after 3

D Slots before 1

We check from the job's deadline backward to find the latest free slot before or on the deadline.

What happens if no free slot is found for a job before its deadline?

A The job is skipped

B The job is scheduled after deadline

C The job is scheduled anyway

D The job's deadline is extended

If no free slot is available before the deadline, the job cannot be scheduled and is skipped.

What is the time complexity of sorting jobs by profit if there are n jobs?

A O(n)

B O(n log n)

C O(log n)

D O(n^2)

Sorting n jobs by profit uses comparison-based sorting, which takes O(n log n) time.

Which of these is NOT a typical property of a job in Job Scheduling with Deadlines?

A Deadline

B Profit

C Duration longer than 1 unit

D Unique job ID

Typically, each job takes exactly 1 unit of time; longer durations require different scheduling approaches.

Describe the greedy approach to solve Job Scheduling with Deadlines.

Think about scheduling the most profitable jobs first and checking slots backward from deadline.

Explain why sorting jobs by profit helps maximize total profit in scheduling.

Consider what happens if you schedule low profit jobs first.