DSA interview question

Job Sequencing

Medium · Algorithms · Topics: greedy, sorting, disjoint set

The problem

A freelancer has n jobs. Each takes one unit of time, has a deadline (it must finish by that time slot) and pays a profit. Only one job can run per slot. Choose and schedule jobs to maximise total profit, and report how many jobs are done and the profit. The greedy: consider jobs from most to least profitable, and put each one in the latest free slot on or before its deadline. Leaving the earlier slots open keeps options for jobs with tighter deadlines.

Example: jobs (id, deadline, profit) (1,4,20), (2,1,10), (3,1,40), (4,1,30) → [2, 60] (jobs 3 and 1).

Function signature

pair<int, int> jobSequencing(const vector<array<int, 3>>& jobs);  // {id, deadline, profit} -> {jobs done, max profit}

Test cases

Input `(id, deadline, profit)`	Output	Explanation
`(1,4,20) (2,1,10) (3,1,40) (4,1,30)`	`[2, 60]`	Job 3 in slot 1, job 1 in slot 4
`(1,2,100) (2,1,19) (3,2,27) (4,1,25) (5,1,15)`	`[2, 127]`	Jobs 1 and 3
`(1,3,10) (2,3,20) (3,3,30)`	`[3, 60]`	All fit
`(1,1,10) (2,1,20)`	`[1, 20]`
`(1,1,5)`	`[1, 5]`

(Confirm: each job takes exactly one slot; slot t covers time (t−1, t]; deadlines ≥ 1.)

How interviewers phrase it

"Given jobs with deadlines and profits, where each job takes one unit of time, find the maximum profit and the number of jobs done" (GeeksforGeeks "Job Sequencing Problem").

Clarifying questions to ask

Does every job take exactly one unit of time? (Yes.)
Can a job run before its deadline? (Yes, in any slot ≤ deadline.)
What should be returned? (The count and the profit.)

Follow-ups to expect

"Why the latest free slot?"
"Why the highest profit first?"
"How do you find the latest free slot quickly?"
"What if jobs had different durations?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview