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

Updated 9 Nov 20266 min read
Job and Activity Selection Interview Questions and Answers: Greedy Traces and Proofs

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

(start, finish)

Maximum compatible count on one resource

Process by increasing finish time

Unit-time job sequencing

(deadline, profit)

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, so lastFinish = 4.

  • Reject B and C because their starts are below 4.

  • Select D, so lastFinish = 7.

  • Reject E, F, and G because their starts are below 7.

  • Select H, so lastFinish = 11.

  • Reject I and J because their starts are below 11.

  • Select K, so lastFinish = 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.

Timeline showing 11 labelled activities, with A, D, H and K highlighted as the four non-overlapping earliest-finish selections.

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.

Profit-sorted job-sequencing diagram showing J1, J3 and J5 placed in slots 2, 1 and 3 for total profit 142.

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.