skip to content

Why is minimising when the later of two loading crews finishes the same hard problem as splitting parcel weights evenly?

level: seniorimportance: should knowfreq 38%

answer

  1. the two loads sum to a constant
  2. makespan is at least half the total
  3. equality means a perfect split exists
  4. Partition reduces to the schedule, not back
  5. two crews already suffice for hardness

basics

~20 s

The two crew loads always sum to the fixed total S, so the later finish is at least S/2 and equals it exactly when the weights split into two halves of S/2. Solving the schedule therefore answers Partition.

solid answer

~40 s

Give two identical crews a pile of parcels; each crew's finish time is its assigned weight, and the pair of loads always sums to the same total `S`. So the later finish - the makespan - can never be below `S/2`, and it hits `S/2` exactly when the weights can be divided into two groups worth `S/2` each. That is the Partition question verbatim. Any routine that returns the optimal makespan therefore answers Partition by one comparison against `S/2`, which means the scheduling problem is at least as hard as Partition and so NP-hard. The hardness is not coming from the crew count - two is already enough - but from the weights themselves.

go deeper

for a junior

Recall that two crews sharing one pile always have loads adding up to the same total, so making the later finish as early as possible means making the two loads as equal as possible.

for a middle

Explain the algebra: the makespan is the larger load, the loads sum to a fixed total, so the makespan is at least half of it and equals half exactly when a perfect split exists.

for a senior

Show the direction of the argument and its consequence: hand the weights to the scheduler, compare against half the total, and you have answered Partition - so the scheduler is at least as hard, and a small crew count is no comfort.

for a principal

Own the framing when a requirement lands: name the family the request belongs to, then move the discussion to the numbers and item counts that decide whether exactness is affordable at all.

## Writing the objective out Two identical crews, `n` parcels, each parcel taking time proportional to its weight, and each crew working through whatever it is given. Let the assigned loads be `L1` and `L2`. Two facts hold for **every** assignment: - `L1 + L2 = S`, the total weight, which the assignment cannot change. - The moment the work is done - the **makespan** - is `max(L1, L2)`. Since the two loads sum to a constant, pushing one down pushes the other up. The makespan is therefore bounded below by half the total, and equals that bound exactly when the two loads are equal. ## Why the two questions coincide Partition asks whether the weights can be divided into two groups of equal total. Set that against the schedule: - A perfect split exists, and the optimal makespan is exactly `S/2`. - No perfect split exists, and every assignment leaves one crew above `S/2`, so the optimal makespan is strictly greater. A worked pair makes it concrete. With weights 8, 7, 6, 5, 4 the total is 30 and `{8, 7}` against `{6, 5, 4}` gives 15 and 15: a perfect split, makespan 15, exactly half. Change the last parcel to 3 and the total is 29, which is odd, so no equal split exists at all; the best assignment is `{8, 7}` against `{6, 5, 3}`, that is 15 against 14, and the makespan is 15 - above half, as the argument predicts. ## What the equivalence establishes, in the right direction Direction is where this argument is usually mangled, so state it carefully: 1. Take any Partition instance - a list of weights. 2. Hand exactly those weights to the two-crew scheduling routine as parcel times. This transformation is trivial and clearly polynomial. 3. Compare the makespan it returns with `S/2`. Equal means yes, greater means no. So **Partition reduces to two-crew scheduling**, and a reduction from A to B makes B at least as hard as A. Partition is NP-hard, therefore two-crew makespan scheduling is NP-hard too. The sentence that inverts this - `scheduling reduces to Partition, so scheduling is hard` - proves nothing, and interviewers listen for it. | the question as asked | its yes-or-no form | where the difficulty lives | |---|---|---| | split the invoice evenly between two accounts | do the amounts divide into two equal groups? | the numeric amounts | | finish the loading as early as possible | is a makespan of B achievable? | the same amounts, same difficulty | | use as few fixed-capacity containers as possible | do B containers suffice? | the amounts plus the capacity | ## Where the hardness is not coming from Several plausible culprits are innocent, and naming them is what separates an understood answer from a memorised one: - **Not the number of crews.** Two is already enough. Adding crews does not create the hardness; it was present at the smallest interesting size. - **Not differing crew speeds or skills.** The crews here are identical. Heterogeneity makes modelling messier but is not the source. - **Not the ordering within a crew.** Each crew's finish time is the sum of what it holds, so the sequence inside a crew is irrelevant to this objective. - **Not the size of the fleet.** A thousand parcels of weight 1 each is trivial. It is the **spread and precision of the weights** that carries the difficulty. ## What a senior engineer does with this The payoff is recognition speed and the correct next sentence. When a requirement says `balance the work across two workers so the last one finishes as early as possible`, the honest response is that the exact version is NP-hard, followed immediately by the question that decides the plan: how large and how precise are the numbers, and how many items are there? Those two answers decide whether an exact method is affordable on the instances you actually see or whether the conversation has to move on to what you settle for instead. It also guards against a false sense of safety when the instance looks small. Two crews and thirty parcels sound trivially enumerable, and for thirty they are; the point of the equivalence is that the difficulty grows with the parcel count in a way that no clever assignment rule removes, because removing it would settle a question about the whole of NP.

  • If the total weight is odd, what is the smallest makespan two crews can possibly achieve?
    With integer weights and an odd total S, the loads cannot be equal, so the larger one is at least (S+1)/2. Whether that value is actually reachable depends on the weights; the parity argument only rules out anything below it.
  • Which direction of reduction would prove nothing here, and why?
    Reducing the scheduling problem to Partition. A reduction from A to B shows B is at least as hard as A, so mapping the schedule onto Partition would only bound the schedule's difficulty from above by Partition's. Hardness transfers from the known-hard problem into the new one, never the reverse.
  • Does the equivalence still hold if each crew also has a fixed capacity it cannot exceed?
    The problem changes shape: with capacities, the question becomes whether the parcels fit at all, which is the packing family rather than the balancing one. It does not become easier - a capacity constraint is one more thing to satisfy, and the numeric difficulty is still there.

saying these in an interview costs you the question

  • States the reduction backwards, mapping the schedule onto Partition
  • Blames the crew count rather than the weights
  • Thinks ordering the parcels within a crew changes the finish time
  • Assumes balancing two workers must be easy because two is small
  • Claims an odd total still permits a makespan of exactly half