Loading…

easyGreedySometimes asked

Jim and the Orders

Q: How do you solve Jim and the Orders using the Brute Force — Repeatedly Scan for the Next-Served Customer approach?

When to use it: Mention to show the selection idea, then replace the repeated scan with a single sort. Mimic the server literally. Repeatedly look through every customer not yet served, pick the one whose serve time `order + prep` is smallest (breaking ties by smaller id), output its id, and mark it served. Do this `n` times. **Why it's correct.** Each round emits exactly the customer the server would serve next, so the full sequence is the true serving order. **Why it's slow.** Finding each minimum costs a full O(n) scan and we do `n` rounds → O(n²). For the constraints (n ≤ 1000) this even passes, but it's the unsorted way of saying 'sort'. **The structure it reveals.** Repeatedly extracting the minimum by a fixed key *is* sorting. Replace the n scans with one comparator sort on `(serveTime, id)` and read the ids off in order — O(n log n), same result. Time complexity: O(n²). Space complexity: O(n).

Q: How do you solve Jim and the Orders using the Greedy — Sort by (Serve Time, Id) (Optimal) approach?

When to use it: The answer they want. Phrase it as 'serve in order of finish time, ties to the lower id — that's just one sort'. Compute each customer's serve time `order[i] + prep[i]`, pair it with the customer's 1-indexed id, sort the pairs by serve time (ties broken by smaller id), and output the ids in that order. **Why sorting by finish time is optimal — the exchange argument.** The server always serves the dish that is ready earliest. Suppose a serving sequence puts a customer with a *later* serve time before one with an *earlier* serve time. Those two are out of finish-time order, so the sequence doesn't match 'earliest-ready served first'. Swap that adjacent pair: now the earlier-finishing dish is served first, which is exactly the server's rule, and no other customer's relative position changes. Repeating these swaps sorts the whole sequence by serve time — and each swap only fixes an out-of-order pair, never creating a new violation. The unique fully-ordered sequence is the answer. **Why ties break by id.** When two serve times are equal the server's rule says lower id first. Encoding `id` as the secondary sort key makes the output deterministic and matches the specification. (A stable sort on a pre-id-ordered list also works, but an explicit secondary key is clearest.) **Why the sum is the only key.** In this single-server-by-completion model each dish's readiness depends solely on its own order and prep times; nothing couples customers. So neither `order` nor `prep` alone determines serving order — only their sum does. Time complexity: O(n log n). Space complexity: O(n).

Greedy Algorithms · 19 of 23 · 8 min

Jim runs a restaurant. There are n customers. Customer i (1-indexed) places an order at time order[i] and the dish takes prep[i] units of time to prepare, so it is served at time `order[i] + prep[i]`.

Server serves whichever dish finishes earliest. If two dishes finish at the same time, the customer with the smaller id is served first.

Return the list of customer ids in the order they are served.

In plain English

Each customer's dish becomes ready at a fixed, independent moment: when they ordered plus how long it cooks. The server simply outputs them in the order those moments occur, and when two coincide it serves the lower-numbered customer first. So we attach to each customer their serve time, sort by (serve time, id), and list the ids.

Examples

Example 1

Input: n = 3, orders = [[1,3],[2,3],[3,3]]
Output: 1 2 3
Note: Serve times: 1+3=4, 2+3=5, 3+3=6. Already increasing → ids in order 1 2 3.

Example 2

Input: n = 5, orders = [[8,1],[4,2],[5,6],[1,1],[3,1]]
Output: 4 5 2 1 3
Note: Serve times: c1=9, c2=6, c3=11, c4=2, c5=4. Sorted ascending → c4(2), c5(4), c2(6), c1(9), c3(11) → 4 5 2 1 3.

Example 3

Input: n = 3, orders = [[1,1],[2,2],[1,1]]
Output: 1 3 2
Note: Serve times: c1=2, c2=4, c3=2. c1 and c3 tie at 2 → smaller id first → 1 then 3, then c2 at 4. Output 1 3 2.

Constraints

1 ≤ n ≤ 1000
1 ≤ order[i], prep[i] ≤ 10⁹
Customer ids are 1..n; ties in serve time break by the smaller id

Clarifying questions4First question: How is serve time computed?Explore questions

Q1.How is serve time computed?
order[i] + prep[i] — the time the order was placed plus the time to prepare it. That sum, not either part alone, is the key.
Q2.Are customer ids 1-indexed?
Yes. The first customer is id 1. The output is these ids, not array positions or serve times.
Q3.How are ties broken?
By the smaller customer id. Two customers finishing at the same time are served lowest-id-first, making the answer deterministic.
Q4.Does the server prepare dishes in parallel or one at a time?
Each dish's finish time is given directly by order + prep, so we don't model contention — we just order by those finish times.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Each customer i (1-indexed) places an order at time `order[i]` and the dish takes `prep[i]` to cook, so it is served at `order[i] + prep[i]`. Customers are served in increasing serve-time, breaking ties by the smaller customer number. Pair each customer's serve time with its id, sort by (serveTime, id), and output the ids in that order. O(n log n) from the sort.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you derive the correct sort key (order + prep) and implement a stable, deterministic tie-break by customer id, while remembering the output is 1-indexed ids.

Where candidates slip

Sorting by prep time or order time alone instead of their sum, mishandling ties (non-deterministic order), or outputting 0-indexed positions or the times themselves.

How to stand out

Note the tie-break makes the result deterministic and that the sum is the only meaningful key for a single-server first-come-by-completion model; mention stability vs explicit id comparison.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Repeatedly Scan for the Next-Served Customer	`O(n²)`	`O(n)`	Mention to show the selection idea, then replace the repeated scan with a single sort.	Read
2	Greedy — Sort by (Serve Time, Id) (Optimal)Optimal	`O(n log n)`	`O(n)`	The answer they want. Phrase it as 'serve in order of finish time, ties to the lower id — that's just one sort'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Compute finish time, sort, emit ids

How to read it:The serve time is order + prep; sort customers by (serveTime, id) and output the ids.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Repeatedly Scan for the Next-Served Customer

TimeO(n²)SpaceO(n)

Mention to show the selection idea, then replace the repeated scan with a single sort.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

At each step, the next customer served is the unserved one with the smallest serve time (ties → smallest id). You could just scan for that customer each round.

2Hint 2Explore hint

Repeat n times: each round scan all remaining customers to find the minimum (serveTime, id), output its id, and mark it served.

3Hint 3Explore hint

That's a selection-sort-style O(n²). Correct, but one comparator-based sort does the same in O(n log n).

A · Core idea

Mimic the server literally. Repeatedly look through every customer not yet served, pick the one whose serve time order + prep is smallest (breaking ties by smaller id), output its id, and mark it served. Do this n times.

Why it's correct. Each round emits exactly the customer the server would serve next, so the full sequence is the true serving order.

Why it's slow. Finding each minimum costs a full O(n) scan and we do n rounds → O(n²). For the constraints (n ≤ 1000) this even passes, but it's the unsorted way of saying 'sort'.

The structure it reveals. Repeatedly extracting the minimum by a fixed key is sorting. Replace the n scans with one comparator sort on (serveTime, id) and read the ids off in order — O(n log n), same result.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3, orders = [[1,1],[2,2],[1,1]]

round 1

min among (2,1),(4,2),(2,3) → (2,1)

Stateoutput 1

Final result1 3 2

C · Code with teaching comments

Reference implementation previewpublic int[] jimOrdersBrute(int[][] orders) { int n = orders.length; boolean[] served = new boolean[n]; int[] result = new int[n]; for (int r = 0; r < n; r++) {Explore the full code

solution.javaJava

Brute Force — Repeatedly Scan for the Next-Served Customer — reference

2 teaching notes

1
public int[] jimOrdersBrute(int[][] orders) {
2
    int n = orders.length;
3
    boolean[] served = new boolean[n];
4
    int[] result = new int[n];
5
    for (int r = 0; r < n; r++) {
6
        int best = -1;
7
        for (int i = 0; i < n; i++) {
8
            if (served[i]) continue;
9
            if (best == -1) { best = i; continue; }
10
            long si = orders[i][0] + (long) orders[i][1];
11
            long sb = orders[best][0] + (long) orders[best][1];
12
            // Pick the smaller serve time, breaking ties by the smaller index (=
13
            // smaller id).
14
            if (si < sb || (si == sb && i < best)) best = i;
15
        }
16
        served[best] = true;
17
        // Store the 1-indexed customer id for this round.
18
        result[r] = best + 1;
19
    }
20
    return result;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

Repeatedly selecting the minimum by a fixed key is selection sort in disguise; a single comparator sort on (serveTime, id) collapses the n scans into O(n log n).

ComplexityO(n²) time, O(n) space — n rounds, each scanning up to n remaining customers to pick the minimum → O(n²). Output buffer is O(n).

E · Edge cases and pitfalls3O(n²) selection loop where a single sort suffices.Explore edge cases

Pitfalls

O(n²) selection loop where a single sort suffices.
Comparing only prep or only order time instead of their sum.
Outputting 0-indexed positions instead of 1-indexed ids.

03.2

Approach 2 of 2 · Optimal

Greedy — Sort by (Serve Time, Id) (Optimal)

TimeO(n log n)SpaceO(n)

The answer they want. Phrase it as 'serve in order of finish time, ties to the lower id — that's just one sort'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each customer's serve time is independent: order + prep. The serving order is just these times sorted ascending.

2Hint 2Explore hint

Attach the 1-indexed id to each serve time so you can output ids, and so ties can be broken deterministically.

3Hint 3Explore hint

Sort the (serveTime, id) pairs by serveTime then id, and emit the ids. One comparator sort, done.

A · Core idea

Compute each customer's serve time order[i] + prep[i], pair it with the customer's 1-indexed id, sort the pairs by serve time (ties broken by smaller id), and output the ids in that order.

Why sorting by finish time is optimal — the exchange argument. The server always serves the dish that is ready earliest. Suppose a serving sequence puts a customer with a later serve time before one with an earlier serve time. Those two are out of finish-time order, so the sequence doesn't match 'earliest-ready served first'. Swap that adjacent pair: now the earlier-finishing dish is served first, which is exactly the server's rule, and no other customer's relative position changes. Repeating these swaps sorts the whole sequence by serve time — and each swap only fixes an out-of-order pair, never creating a new violation. The unique fully-ordered sequence is the answer.

Why ties break by id. When two serve times are equal the server's rule says lower id first. Encoding id as the secondary sort key makes the output deterministic and matches the specification. (A stable sort on a pre-id-ordered list also works, but an explicit secondary key is clearest.)

Why the sum is the only key. In this single-server-by-completion model each dish's readiness depends solely on its own order and prep times; nothing couples customers. So neither order nor prep alone determines serving order — only their sum does.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5, orders = [[8,1],[4,2],[5,6],[1,1],[3,1]]

Array state

before sort

pairs (serve, id)

(9,1)

[0]

(6,2)

[1]

(11,3)

[2]

(2,4)

[3]

(4,5)

[4]

Current pointerResolved stateNot processed

Final result4 5 2 1 3

C · Code with teaching comments

solution.javaJava

Greedy — Sort by (Serve Time, Id) (Optimal) — optimal

4 teaching notes

1
public int[] jimOrders(int[][] orders) {
2
    int n = orders.length;
3
    Integer[] ids = new Integer[n];
4
    for (int i = 0; i < n; i++) ids[i] = i;
5
    Arrays.sort(ids, (a, b) -> {
6
        // Serve time = order + prep; cast to long since both can reach 10⁹.
7
        long sa = orders[a][0] + (long) orders[a][1];
8
        long sb = orders[b][0] + (long) orders[b][1];
9
        // Primary key: earlier serve time first.
10
        if (sa != sb) return Long.compare(sa, sb);
11
        // Tie-break by smaller index (= smaller id) for determinism.
12
        return Integer.compare(a, b);
13
    });
14
    int[] result = new int[n];
15
    for (int i = 0; i < n; i++) result[i] = ids[i] + 1;
16
    return result;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

The entire problem is choosing the comparator: (order + prep, id). Once the right finish-time key is identified, an O(n log n) sort produces the serving order directly. Reusable kernel: 'process jobs by independent completion time, deterministic tie-break, emit indices'.

ComplexityO(n log n) time, O(n) space — Building the key array is O(n); the comparator sort is O(n log n) and dominates; emitting ids is O(n). O(n) auxiliary space for the pairs.

E · Edge cases and pitfalls6all equal serve times — Every pair ties → output is ids in ascending order 1,2,…,n.Explore edge cases

Edge cases handled

all equal serve timesEvery pair ties → output is ids in ascending order 1,2,…,n.
n = 1Single customer → output [1] regardless of times.
tie between c1 and c3 at same serve timeSecondary key id puts c1 before c3 (e.g. example 3 → 1 3 2).

Pitfalls

Sorting by prep or order time alone instead of their sum.
Non-deterministic tie handling — must break ties by smaller id.
Returning serve times or 0-indexed positions instead of 1-indexed ids; also use long to avoid 10⁹ + 10⁹ overflow.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] jimOrders(int[][] orders) { int n = orders.length; Integer[] ids = new Integer[n]; for (int i = 0; i < n; i++) ids[i] = i; Arrays.sort(ids, (a, b) -> {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Sorting by the wrong key

The serve time is order + prep. Sorting on prep alone (or order alone) produces the wrong serving sequence.

Explore the code comparison

Don't write this

ids = sorted(range(n), key=lambda i: orders[i][1])  # prep only

Write this instead

ids = sorted(range(n), key=lambda i: (orders[i][0] + orders[i][1], i))

Missing the id tie-break

When two serve times match, the lower id must come first. Omitting the secondary key makes ordering non-deterministic.

Explore the code comparison

Don't write this

Arrays.sort(ids, (a, b) -> Long.compare(
    orders[a][0] + (long) orders[a][1],
    orders[b][0] + (long) orders[b][1]));

Write this instead

Arrays.sort(ids, (a, b) -> {
    long sa = orders[a][0] + (long) orders[a][1];
    long sb = orders[b][0] + (long) orders[b][1];
    if (sa != sb) return Long.compare(sa, sb);
    return Integer.compare(a, b);
});

Integer overflow on the sum

order and prep can each be 10⁹; their int sum overflows. Cast to long before adding.

Explore the code comparison

Don't write this

int serve = orders[i][0] + orders[i][1];  // can overflow int

Write this instead

long serve = orders[i][0] + (long) orders[i][1];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy by completion time: sort on a derived key (serveTime, id) and read off the ids

Code pattern to memorize

serve[i] = order[i] + prep[i]
build list of (serve[i], id=i+1)
sort by serve ascending, then id ascending
return the ids in sorted order

Rules to remember

1Serve time = order (placement) time + preparation (cook) time. That single sum is the sort key.
2Customers are 1-indexed in the output — id = array position + 1.
3Ties on serve time break by the SMALLER customer id (earlier customer number served first).
4Sort the (serveTime, id) pairs; the output is the sequence of ids, not the serve times.
5The order in which customers appear in the input doesn't matter beyond fixing their ids.

Use this pattern when

Order events by a computed completion/finish time
A deterministic tie-break (by id / index) is required
The answer is the permutation of indices induced by sorting a derived key
Single-server scheduling where each job's finish time is independent

Choose another pattern when

Jobs have dependencies or release constraints affecting each other → scheduling DP, not a sort
You must minimise total/weighted completion time by choosing order → shortest-job-first, a different key
Serve time isn't a simple sum (e.g. server can batch) → model changes
Ties are broken arbitrarily / not by id → comparator differs

Interview takeaway

When each job's finish time is independent and you just report processing order, compute the finish key, sort with a deterministic tie-break, and emit the indices. The whole problem is choosing the right comparator: (orderTime + prepTime, id).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternGreedy by completion time: when each job's finish moment is independent, sort on the derived key (order + prep, id) and emit indices. The adjacent-swap exchange argument shows earliest-finish-first is the unique correct order; the id key makes ties deterministic.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Priyanka and Toys
Another sort-first greedy — sort then sweep with a simple rule.
Greedy Florist
Sort on a derived key and assign, justified by an exchange argument.
Minimum Time to Finish All Jobs (SJF)
Coming soon
When minimising total completion time you sort by prep alone — a different key.
Task Scheduler
Coming soon
Ordering jobs by a computed priority to optimise a schedule.

Same pattern

←

Grid Challenge

Continue · Next problem

Largest Permutation

easyGreedySometimes asked

Jim and the Orders

Greedy Algorithms · 19 of 23 · 8 min

Server serves whichever dish finishes earliest. If two dishes finish at the same time, the customer with the smaller id is served first.

Return the list of customer ids in the order they are served.

In plain English

Examples

Example 1

Input: n = 3, orders = [[1,3],[2,3],[3,3]]
Output: 1 2 3
Note: Serve times: 1+3=4, 2+3=5, 3+3=6. Already increasing → ids in order 1 2 3.

Example 2

Input: n = 5, orders = [[8,1],[4,2],[5,6],[1,1],[3,1]]
Output: 4 5 2 1 3
Note: Serve times: c1=9, c2=6, c3=11, c4=2, c5=4. Sorted ascending → c4(2), c5(4), c2(6), c1(9), c3(11) → 4 5 2 1 3.

Example 3

Input: n = 3, orders = [[1,1],[2,2],[1,1]]
Output: 1 3 2
Note: Serve times: c1=2, c2=4, c3=2. c1 and c3 tie at 2 → smaller id first → 1 then 3, then c2 at 4. Output 1 3 2.

Constraints

1 ≤ n ≤ 1000
1 ≤ order[i], prep[i] ≤ 10⁹
Customer ids are 1..n; ties in serve time break by the smaller id

Clarifying questions4First question: How is serve time computed?Explore questions

Q1.How is serve time computed?
order[i] + prep[i] — the time the order was placed plus the time to prepare it. That sum, not either part alone, is the key.
Q2.Are customer ids 1-indexed?
Yes. The first customer is id 1. The output is these ids, not array positions or serve times.
Q3.How are ties broken?
By the smaller customer id. Two customers finishing at the same time are served lowest-id-first, making the answer deterministic.
Q4.Does the server prepare dishes in parallel or one at a time?
Each dish's finish time is given directly by order + prep, so we don't model contention — we just order by those finish times.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you derive the correct sort key (order + prep) and implement a stable, deterministic tie-break by customer id, while remembering the output is 1-indexed ids.

Where candidates slip

Sorting by prep time or order time alone instead of their sum, mishandling ties (non-deterministic order), or outputting 0-indexed positions or the times themselves.

How to stand out

Note the tie-break makes the result deterministic and that the sum is the only meaningful key for a single-server first-come-by-completion model; mention stability vs explicit id comparison.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Repeatedly Scan for the Next-Served Customer	`O(n²)`	`O(n)`	Mention to show the selection idea, then replace the repeated scan with a single sort.	Read
2	Greedy — Sort by (Serve Time, Id) (Optimal)Optimal	`O(n log n)`	`O(n)`	The answer they want. Phrase it as 'serve in order of finish time, ties to the lower id — that's just one sort'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Compute finish time, sort, emit ids

How to read it:The serve time is order + prep; sort customers by (serveTime, id) and output the ids.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Repeatedly Scan for the Next-Served Customer

TimeO(n²)SpaceO(n)

Mention to show the selection idea, then replace the repeated scan with a single sort.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

At each step, the next customer served is the unserved one with the smallest serve time (ties → smallest id). You could just scan for that customer each round.

2Hint 2Explore hint

Repeat n times: each round scan all remaining customers to find the minimum (serveTime, id), output its id, and mark it served.

3Hint 3Explore hint

That's a selection-sort-style O(n²). Correct, but one comparator-based sort does the same in O(n log n).

A · Core idea

Why it's correct. Each round emits exactly the customer the server would serve next, so the full sequence is the true serving order.

Why it's slow. Finding each minimum costs a full O(n) scan and we do n rounds → O(n²). For the constraints (n ≤ 1000) this even passes, but it's the unsorted way of saying 'sort'.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3, orders = [[1,1],[2,2],[1,1]]

round 1

min among (2,1),(4,2),(2,3) → (2,1)

Stateoutput 1

Final result1 3 2

C · Code with teaching comments

solution.javaJava

Brute Force — Repeatedly Scan for the Next-Served Customer — reference

2 teaching notes

1
public int[] jimOrdersBrute(int[][] orders) {
2
    int n = orders.length;
3
    boolean[] served = new boolean[n];
4
    int[] result = new int[n];
5
    for (int r = 0; r < n; r++) {
6
        int best = -1;
7
        for (int i = 0; i < n; i++) {
8
            if (served[i]) continue;
9
            if (best == -1) { best = i; continue; }
10
            long si = orders[i][0] + (long) orders[i][1];
11
            long sb = orders[best][0] + (long) orders[best][1];
12
            // Pick the smaller serve time, breaking ties by the smaller index (=
13
            // smaller id).
14
            if (si < sb || (si == sb && i < best)) best = i;
15
        }
16
        served[best] = true;
17
        // Store the 1-indexed customer id for this round.
18
        result[r] = best + 1;
19
    }
20
    return result;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

Repeatedly selecting the minimum by a fixed key is selection sort in disguise; a single comparator sort on (serveTime, id) collapses the n scans into O(n log n).

ComplexityO(n²) time, O(n) space — n rounds, each scanning up to n remaining customers to pick the minimum → O(n²). Output buffer is O(n).

E · Edge cases and pitfalls3O(n²) selection loop where a single sort suffices.Explore edge cases

Pitfalls

O(n²) selection loop where a single sort suffices.
Comparing only prep or only order time instead of their sum.
Outputting 0-indexed positions instead of 1-indexed ids.

03.2

Approach 2 of 2 · Optimal

Greedy — Sort by (Serve Time, Id) (Optimal)

TimeO(n log n)SpaceO(n)

The answer they want. Phrase it as 'serve in order of finish time, ties to the lower id — that's just one sort'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each customer's serve time is independent: order + prep. The serving order is just these times sorted ascending.

2Hint 2Explore hint

Attach the 1-indexed id to each serve time so you can output ids, and so ties can be broken deterministically.

3Hint 3Explore hint

Sort the (serveTime, id) pairs by serveTime then id, and emit the ids. One comparator sort, done.

A · Core idea

Compute each customer's serve time order[i] + prep[i], pair it with the customer's 1-indexed id, sort the pairs by serve time (ties broken by smaller id), and output the ids in that order.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5, orders = [[8,1],[4,2],[5,6],[1,1],[3,1]]

Array state

before sort

pairs (serve, id)

(9,1)

[0]

(6,2)

[1]

(11,3)

[2]

(2,4)

[3]

(4,5)

[4]

Current pointerResolved stateNot processed

Final result4 5 2 1 3

C · Code with teaching comments

solution.javaJava

Greedy — Sort by (Serve Time, Id) (Optimal) — optimal

4 teaching notes

1
public int[] jimOrders(int[][] orders) {
2
    int n = orders.length;
3
    Integer[] ids = new Integer[n];
4
    for (int i = 0; i < n; i++) ids[i] = i;
5
    Arrays.sort(ids, (a, b) -> {
6
        // Serve time = order + prep; cast to long since both can reach 10⁹.
7
        long sa = orders[a][0] + (long) orders[a][1];
8
        long sb = orders[b][0] + (long) orders[b][1];
9
        // Primary key: earlier serve time first.
10
        if (sa != sb) return Long.compare(sa, sb);
11
        // Tie-break by smaller index (= smaller id) for determinism.
12
        return Integer.compare(a, b);
13
    });
14
    int[] result = new int[n];
15
    for (int i = 0; i < n; i++) result[i] = ids[i] + 1;
16
    return result;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n log n) time, O(n) space — Building the key array is O(n); the comparator sort is O(n log n) and dominates; emitting ids is O(n). O(n) auxiliary space for the pairs.

E · Edge cases and pitfalls6all equal serve times — Every pair ties → output is ids in ascending order 1,2,…,n.Explore edge cases

Edge cases handled

all equal serve timesEvery pair ties → output is ids in ascending order 1,2,…,n.
n = 1Single customer → output [1] regardless of times.
tie between c1 and c3 at same serve timeSecondary key id puts c1 before c3 (e.g. example 3 → 1 3 2).

Pitfalls

Sorting by prep or order time alone instead of their sum.
Non-deterministic tie handling — must break ties by smaller id.
Returning serve times or 0-indexed positions instead of 1-indexed ids; also use long to avoid 10⁹ + 10⁹ overflow.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Sorting by the wrong key

The serve time is order + prep. Sorting on prep alone (or order alone) produces the wrong serving sequence.

Explore the code comparison

Don't write this

ids = sorted(range(n), key=lambda i: orders[i][1])  # prep only

Write this instead

ids = sorted(range(n), key=lambda i: (orders[i][0] + orders[i][1], i))

Missing the id tie-break

When two serve times match, the lower id must come first. Omitting the secondary key makes ordering non-deterministic.

Explore the code comparison

Don't write this

Arrays.sort(ids, (a, b) -> Long.compare(
    orders[a][0] + (long) orders[a][1],
    orders[b][0] + (long) orders[b][1]));

Write this instead

Arrays.sort(ids, (a, b) -> {
    long sa = orders[a][0] + (long) orders[a][1];
    long sb = orders[b][0] + (long) orders[b][1];
    if (sa != sb) return Long.compare(sa, sb);
    return Integer.compare(a, b);
});

Integer overflow on the sum

order and prep can each be 10⁹; their int sum overflows. Cast to long before adding.

Explore the code comparison

Don't write this

int serve = orders[i][0] + orders[i][1];  // can overflow int

Write this instead

long serve = orders[i][0] + (long) orders[i][1];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy by completion time: sort on a derived key (serveTime, id) and read off the ids

Code pattern to memorize

serve[i] = order[i] + prep[i]
build list of (serve[i], id=i+1)
sort by serve ascending, then id ascending
return the ids in sorted order

Rules to remember

1Serve time = order (placement) time + preparation (cook) time. That single sum is the sort key.
2Customers are 1-indexed in the output — id = array position + 1.
3Ties on serve time break by the SMALLER customer id (earlier customer number served first).
4Sort the (serveTime, id) pairs; the output is the sequence of ids, not the serve times.
5The order in which customers appear in the input doesn't matter beyond fixing their ids.

Use this pattern when

Order events by a computed completion/finish time
A deterministic tie-break (by id / index) is required
The answer is the permutation of indices induced by sorting a derived key
Single-server scheduling where each job's finish time is independent

Choose another pattern when

Jobs have dependencies or release constraints affecting each other → scheduling DP, not a sort
You must minimise total/weighted completion time by choosing order → shortest-job-first, a different key
Serve time isn't a simple sum (e.g. server can batch) → model changes
Ties are broken arbitrarily / not by id → comparator differs

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Priyanka and Toys
Another sort-first greedy — sort then sweep with a simple rule.
Greedy Florist
Sort on a derived key and assign, justified by an exchange argument.
Minimum Time to Finish All Jobs (SJF)
Coming soon
When minimising total completion time you sort by prep alone — a different key.
Task Scheduler
Coming soon
Ordering jobs by a computed priority to optimise a schedule.

Same pattern

←

Grid Challenge

Continue · Next problem

Largest Permutation