Micro-questions over the selection and scheduling module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. Hire K workers

1. State the problem.

Answer

Hire people. Each has a quality and a minimum wage. Everyone hired is paid the same rate per unit of quality, and nobody may be paid below their own minimum. Which cost least in total?

2. What is the instinctive answer, and why is it wrong?

Answer

“Take the cheapest advertised wages.” Wrong because one expensive-per-unit person raises the rate for everybody.

3. Work the example: A(10, 70), B(20, 140), C(5, 60), .

Answer

Ratios 7.00, 7.00, 12.00. A+B = . A+C = . B+C = . A+C wins, despite containing the worst rate.

4. Why does the cheap rate of A+B lose?

Answer

B’s high quality. You pay for quality you do not need.

5. State the whole difficulty in one sentence.

Answer

The cost of a group is not the sum of its members’ costs — it is a product of two things that pull in opposite directions.

6. Give the cost formula.

Answer

7. Say it in words.

Answer

The bill is the group’s worst rate multiplied by the group’s total quality. One person sets the price; everyone contributes to the volume.

8. Give the greedy in five steps.

Answer
  1. Sort everyone by ratio, ascending.
  2. The worker you are at has the largest ratio seen so far, so they set the rate.
  3. Given that rate, you want the smallest qualities among those seen.
  4. Maintain them with a max-heap of size — push, and pop the largest when it exceeds .
  5. Once the heap holds exactly , candidate cost = rate × sum_of_heap. Keep the minimum.

9. Why is it correct?

Answer

Every group has some member with the maximum ratio. Fixing that member fixes the rate, leaving only the choice of which others — for which you obviously want the smallest qualities. Iterating over every possible rate-setter considers every group that could be optimal.

10. What is the cost?

Answer

to sort plus to sweep.

11. How often is “take the cheapest wages” wrong?

Answer

130 of 400 random instances — nearly a third. Not an exotic corner case.


B. Interval scheduling

12. State the problem.

Answer

Given meetings with start and end times, fit in as many non-overlapping meetings as possible.

13. Which sort key is correct?

Answer

Earliest END time.

14. Why does earliest START fail?

Answer

It takes the meeting running 0–10 and is then blocked for the whole day — one meeting instead of two.

15. Why does shortest DURATION fail?

Answer

On [(0,5),(4,6),(5,10)] the short middle meeting blocks both long ones — one instead of two.

16. What is the testing lesson here?

Answer

Shortest-duration ties with the correct answer on the first example and fails on the second. Each wrong key fails on some input and ties on others; only “earliest end” survives both.

17. Give the exchange argument.

Answer

Let be the earliest-finishing meeting. Take any optimal solution sorted by end time; ends no later than , so replacing with leaves every later meeting still compatible. The modified set is valid and the same size, so still optimal. Recurse.

18. State the intuition in one sentence.

Answer

Finishing earliest leaves the most room for everything else, and nothing is lost by preferring it.


C. Select the most vs cover them all

19. What is the opposite problem, over the same input?

Answer

How many rooms do you need to hold all of them? Section 2 discards conflicting meetings; this one pays for them.

20. What is the answer?

Answer

The peak number of simultaneous meetings.

21. Describe the sweep.

Answer

Build events: at every start, at every end. Sort so that precedes at the same instant. Accumulate and track the maximum.

22. Why must precede ?

Answer

A meeting ending at 10 and another starting at 10 need one room, not two.


D. Traps

23. What problem shape has the “worst member sets the price” structure?

Answer

Any problem where one member’s constraint applies to the whole group. The naive per-member sum is wrong there.

24. Why negate when using Python’s heapq here?

Answer

heapq is a min-heap, and in the hiring sweep you are discarding the largest qualities — so the heap must surrender its maximum. Negation inverts it.

25. What is the floating-point ratio trap, and the fix?

Answer

Two candidates with equal ratios can compare unequal after division. Compare against to stay in integers.

26. Hire-K is greedy. What similar-looking problem is not?

Answer

The assignment problem — one person per job, each pair with its own cost. Greedy is wrong for it; it needs the Hungarian algorithm or min-cost max-flow.

27. What should you do if you cannot write the exchange argument?

Answer

Use dynamic programming. A greedy that passes your tests without an argument is a guess — slower and correct beats fast and wrong.

28. Summarise the module in one sentence.

Answer

The sort key is the greedy algorithm — and choosing it correctly means proving an exchange argument, not testing one example.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Greedy Algorithms