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

Recall & Review

beginner

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

The goal is to schedule jobs to maximize total profit while ensuring each job is completed before its deadline.

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 earned if completed on time.

intermediate

Why do we sort jobs by profit in descending order in the Job Scheduling algorithm?

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

intermediate

How do we decide the time slot for a job in the Job Scheduling with Deadlines algorithm?

We assign the job to the latest available time slot before its deadline to keep earlier slots free for other jobs.

beginner

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

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

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

A Sort jobs by profit in descending order

B Sort jobs by deadline in ascending order

C Assign jobs randomly

D Schedule jobs with earliest deadlines first

Sorting jobs by profit ensures we prioritize the most profitable jobs first.

If a job's deadline is 3, which time slots can it be assigned to?

A Any slot from 1 to 3

B Only slot 1

C Any slot after 3

D Only slot 3

The job can be assigned to any free slot before or on its deadline.

What happens if no free slot is available before a job's deadline?

A The job is scheduled anyway

B The job is skipped and not scheduled

C The job is scheduled after the deadline

D The job's deadline is extended

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

Which algorithmic approach does Job Scheduling with Deadlines use?

A Dynamic Programming

B Divide and Conquer

C Backtracking

D Greedy Algorithm

It uses a greedy approach by scheduling the most profitable jobs first.

What is the output of the Job Scheduling with Deadlines algorithm?

A Sum of all deadlines

B Total number of jobs

C List of jobs scheduled with maximum profit

D List of jobs sorted by deadline

The output is the list of jobs scheduled to maximize profit.

Explain the steps to solve the Job Scheduling with Deadlines problem using a greedy approach.

Think about how to pick jobs and assign time slots.

Describe how to track free time slots when scheduling jobs with deadlines.

Consider how to efficiently find a free slot before deadline.