Job and Activity Selection Interview Questions and Answers: Greedy Traces and Proofs
Learn to separate activity selection from unit-time job sequencing, trace both greedy algorithms, defend their proofs, and handle common interview follow-ups.
KnowledgeGate Team
Exam prep & CS education

An interviewer who says "job selection" may mean unit-time jobs with deadlines and profits, or may actually mean activity selection over time intervals. Naming an algorithm before confirming the objective is risky. A strong answer first clarifies the variant, then gives the rule, a complete trace, a proof idea, complexity, and the constraint changes that break the greedy method.
Job selection and activity selection are not the same problem
Problem | Input | Objective | Greedy rule |
|---|---|---|---|
Activity selection |
| Maximum compatible count on one resource | Process by increasing finish time |
Unit-time job sequencing |
| Maximum total profit | Process by decreasing profit and use the latest free legal slot |
The clarification script is: "Are all jobs one unit long, is each deadline an integer slot by which a job must finish, and are we maximising profit? Or are these arbitrary intervals and we are maximising the number that do not overlap?" This distinction matters throughout coding and DSA preparation because the methods are not interchangeable.
Both preserve future capacity, but in different ways. Activity selection leaves the longest possible timeline suffix by choosing the earliest finish. Job sequencing protects early slots by placing each profitable job as late as its deadline allows.
Activity selection interview answer, traced from input to optimum
Take the already finish-sorted activities A(1,4), B(3,5), C(0,6), D(5,7), E(3,9), F(5,9), G(6,10), H(8,11), I(8,12), J(2,14), K(12,16). Touching endpoints are compatible because next.start >= last.finish.
Select
A, solastFinish = 4.Reject
BandCbecause their starts are below 4.Select
D, solastFinish = 7.Reject
E,F, andGbecause their starts are below 7.Select
H, solastFinish = 11.Reject
IandJbecause their starts are below 11.Select
K, solastFinish = 16.
The progression is 4 -> 7 -> 11 -> 16, and the result is {A,D,H,K}, count 4.
The proof is an exchange argument. If an optimal schedule begins with an activity that finishes later than A, replace that activity with A. The replacement cannot reduce the room for everything that follows. Repeating the exchange establishes the greedy schedule. The same proof pattern is developed in Greedy Algorithms Explained.
Sorting costs O(n log n) and scanning costs O(n). If the input is already finish-sorted, the total is O(n). Auxiliary space can be O(1) apart from the returned list.

Job sequencing with deadlines, traced to maximum profit
Use five unit-time jobs: J1(d2,p100), J2(d1,p19), J3(d2,p27), J4(d1,p25), J5(d3,p15). Slots are 1, 2, 3, and a deadline d permits any slot at most d.
Descending profit gives J1(100), J3(27), J4(25), J2(19), J5(15). Put J1 in slot 2. Put J3 in slot 1 because slot 2 is occupied. Reject J4, then J2, because neither has a free slot at or before 1. Put J5 in slot 3. The chronological schedule is [J3,J1,J5], and its profit is 27 + 100 + 15 = 142, with three jobs completed.
The latest-free-slot rule preserves earlier capacity for tighter deadlines. Putting J1 in slot 1 would occupy the only place available to deadline-1 jobs without increasing its profit. With a backward slot scan, the cost is O(n log n + nD), where D = min(maxDeadline,n). Since D <= n, the worst case is O(n^2) after sorting. A disjoint-set structure is the standard faster follow-up.

Six interview questions with concise model answers
Why does earliest finish time work?
It leaves the largest suffix for later activities. The exchange argument above shows that replacing a later-finishing first choice cannot hurt an optimum. Sorting plus scanning is O(n log n), or O(n) for finish-sorted input.
Why not choose the activity that starts earliest?
For X(0,10), A(1,2), B(2,3), C(3,4), D(4,5), earliest start returns only X; earliest finish returns {A,B,C,D}, count 4. The correct algorithm retains the same O(n log n) sorting bound.
Why not choose the shortest activity?
For A(0,3), B(2,4), C(3,6), shortest duration chooses only B, while {A,C} is compatible and has count 2. Duration does not measure how much useful suffix remains. Earliest-finish sorting and scanning still costs O(n log n).
Why place a profitable job in the latest free slot?
It preserves earlier slots for tighter deadlines. With A(d2,p100) and B(d1,p99), putting A in slot 2 leaves slot 1 for B and earns 199; putting A in slot 1 leaves B unscheduled and earns only 100. The baseline backward-scan implementation costs O(n log n + nD).
Can earliest deadline first replace profit sorting?
No. With P(d1,p10), Q(d2,p100), R(d2,p99), taking P then Q earns 110, while [R,Q] earns 99 + 100 = 199. Profit sorting with latest placement keeps the baseline O(n log n + nD) bound.
What about ties?
For equal activity finishes, either choice leaves the same suffix, subject to compatibility with the last selection. For equal job profits, either order preserves profit priority; apply the latest-slot rule and return one valid optimum. Tie handling does not change either algorithm's complexity.
Implementation blueprint and edge cases
Activity selection is: sort by finish ascending, set lastFinish = -infinity, scan once, and accept an activity when start >= lastFinish, then update lastFinish. If the first activity is selected before the loop, start scanning at the second.
Job sequencing is: discard non-positive-profit jobs when no job is compulsory; sort by profit descending; create slots 1..D, where D = min(maxDeadline,n); and scan backward from min(deadline,D) for each job. Return the chronological schedule and summed profit.
Handle empty or unsorted input, one or zero-length intervals, duplicate intervals, deadlines <= 0, deadlines above n, and zero or negative profit explicitly. Keep the declared endpoint rule throughout the trace.
Where the greedy answer stops working
Maximum-value activities require weighted interval scheduling with dynamic programming, because earliest finish maximises count, not value. Unequal job durations break the one-slot placement invariant. Multiple rooms may turn the task into interval partitioning.
Common mistakes are sorting activities by start, sorting jobs by deadline, using > instead of the declared >=, placing a job earlier than necessary, returning profit order instead of chronological order, and claiming O(n log n) while scanning up to D slots per job.
A 90-second answer structure and focused practice loop
Speak in this order: clarify the variant and objective, state the greedy key, give the selection or placement rule, justify its invariant, report time and space complexity, then name the first constraint change that breaks it. Rehearse once for each problem.
The Job and Activity Selection question set gives you a focused practice pass. First classify each variant without solving it, then trace selections on paper, then explain one proof and one counterexample aloud.Job and Activity Selection solved questions for that worked-practice pass, and combine it with OS, DBMS, CN, and OOP revision for broader interviews.
Short version and next step
Earliest finish gives the maximum number of compatible activities. Descending profit plus the latest legal slot gives maximum profit for unit-time deadline jobs. Here the answers are {A,D,H,K}, count 4, and [J3,J1,J5], profit 142.
Reproduce both traces without looking, explain the exchange argument in one minute, and implement both algorithms. Continue with DSA Using Java for interview-focused DSA, or use Coding for Placement for a broader multi-language placement route.
Keep learning
Job Sequencing and Activity Selection MCQs: 12 Solved Questions with Explanations (GATE/NET/ISRO)
Solve 12 activity selection and job sequencing questions step by step. The set covers greedy rules, compatibility, room counting, feasible schedules and maximum-profit slotting.
Pumping Lemma for Regular Languages: Quantifiers, Worked Proofs and GATE Traps
Learn who chooses the pumping length, witness, split and index. Then follow two checked examples and a reusable method for proving a language is not regular.
Regularity Identification in Automata Theory: DFA/NFA Tests and Worked Proofs
Learn how to classify languages by the memory they need, construct a product DFA, and prove a genuinely non-regular language with pumping and Myhill-Nerode.
Applications of Mathematical Induction in Inequalities and Recurrence Relations: Worked Proofs
Learn how to choose a valid base index, complete an inequality step, and verify closed forms for first-order and second-order recurrences.





