CodeWithYash

Intermediate · Module 16 · Lesson 5

Resource assignment

Sort demands and resources before matching.

15–25 min readLesson 93 of 123

Lesson 93 of 123

1d streak

Theory lesson · Step-by-step

Understand Resource assignment

Sort demands and resources before matching.

Worked approach

Trace the reasoning step by step

  1. 1State the candidate ordering and local choice made by Resource assignment.
  2. 2Identify the feasibility condition maintained by the partial solution.
  3. 3Use an exchange or stays-ahead argument to justify the choice.
  4. 4Commit the choice and remove candidates it makes impossible.
  5. 5Search for a counterexample before trusting the greedy rule.

Concrete example

Assign cookies [1,2] to demands [1,2,3].

  1. 1Sort both lists.
  2. 2Cookie 1 satisfies demand 1.
  3. 3Cookie 2 satisfies demand 2.

Two demands are satisfied; saving a larger cookie would not improve the count.

What must remain true (Loop Invariant)

After every choice in Resource assignment, the partial solution can still be extended to an optimum under the proved exchange or stays-ahead argument.

Cost Model

Complexity & Trade-offs

Sort and match
O(n log n + m log m)
O(1) auxiliary
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Scheduling, reachability, coding, matching resources, and minimum-cost growth.
  • Problems with an exchange proof or matroid-like safe choices.
  • Online decisions that maintain a best frontier.

Common mistakes

  • Choosing a plausible local optimum without a proof.
  • Using the wrong sorting key.
  • Applying greedy reasoning when choices interact through future state.

Practice prompts

  • Reproduce the worked Resource assignment example without looking at the trace.
  • Change one input condition and explain whether the Resource assignment invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.