You have 6 minutes and three chores that take 3, 6, and 3 minutes — how many can you finish? The instinct says "do the quick ones first": sort the list, then start from the front. That instinct is greediness. But contests do not grade on instinct: why does "shortest first" always deliver the maximum count? If it fails even once, you lose the whole problem. This note uses CCC 2013's Time on Task to walk through the standard proof behind this kind of greedy — the exchange argument. By the end you will recognize it as the exact same pattern that justified sort-and-pair in the same-week Tandem Bicycle walkthrough.

The Common Mistake

total_time = int(input())
count = int(input())
chores = [int(input()) for _ in range(count)]

done = 0
for chore in chores:          # in input order
    if chore <= total_time:
        total_time -= chore
        done += 1
print(done)

The flaw is letting the input decide the order. Run it on official sample 2 (T=6, chores 5, 4, 3, 2, 1 minutes): it does the 5-minute chore first, wastes the remaining minute, and finishes only 1 chore — while the answer is 3 (1+2+3). The same data gives different answers under different orders, so the order is itself part of the decision. Leaving it to the input format means abandoning half the problem.

The Core Idea

State the task precisely: choose a subset of chores whose total duration ≤ T, with the largest possible count. Note we are maximizing the count, not minimizing the total time — those are different classic problems, and only the count is asked here.

Now the key lemma: among all selections of exactly k chores, the k shortest have the minimum total duration. Proof by one replacement: take any selection S of k chores that is not "the k shortest". Then some shorter chore x is unselected while a longer chore y is selected. Swap y for x: the count is still k, and the total does not grow (x ≤ y). Repeating finitely many times turns any selection into "the k shortest", never increasing the total. Lemma proved.

By the lemma, the problem becomes a scan: sort ascending, accumulate prefix sums. Let S(k) be the sum of the k shortest; S(k) is non-decreasing, and the maximum finishable count is exactly "the last k with S(k) ≤ T". And by the other side of the lemma: if the k shortest already exceed T, no k chores can fit (any k chores sum to at least S(k)). Both directions close — the greedy is not just "an answer", it equals the optimum.

Walk sample 2 by hand: sorted [1,2,3,4,5], prefix sums 1, 3, 6, 10, 15. With T=6 the first three fit exactly, the fourth breaks the budget — answer 3, matching the official output. Sample 1 (T=6, [3,6,3]) sorts to [3,3,6], prefix sums 3, 6, 12, answer 2.

The Recommended Solution

total_time = int(input())
count = int(input())
chores = [int(input()) for _ in range(count)]

chores.sort()

used = 0
done = 0
for chore in chores:
    if used + chore <= total_time:
        used += chore
        done += 1
    else:
        break

print(done)

6
3
3
6
3
2

Three details worth keeping. First, break instead of continue: after sorting, everything later is longer — if the current chore does not fit, nothing after it will either. Second, accumulate into a separate used rather than rewriting total_time — the remaining budget stays inspectable while debugging. Third, C ≤ 100, each chore ≤ 100000, T ≤ 100000, so the sums fit easily in an int; but if the limits grow, big-integer accumulation is cheap insurance.

The Same Proof: From Pairing to Counting

Zoom out: this problem and the same-week Tandem Bicycle share one mold. Tandem Bicycle pairs N tandem riders to minimize or maximize the total speed; its proof swaps crossed pairs back into same order and shows the total never worsens. Time on Task swaps any k chores for the k shortest and shows the budget never worsens. Both say "there exists a tidy solution that is no worse": turn any solution into the tidy one step by step, then identify the best among tidy ones. Whenever you see sorting plus greedy, ask "does one replacement step ever make it worse?" — if you can answer, write the code. That question is the line between a slogan and a tool.

Side by Side

Practice

1. Change T to 7 in sample 1: predict the answer with prefix sums, then verify by running. (Can you finish the two 3-minute chores? Does the 6-minute one fit after that? Work it out.)
2. With chores [4, 4, 4, 4] and T=9, how many fit? Use the lemma to explain why shortest-first is still correct here.
3. Challenge: if every chore requires an extra 1-minute rest (real cost = duration + 1), does "sort and scan from the front" still hold? Which single line would you change? (Hint: +1 per chore is like the budget paying an extra "done" minutes in advance…)

One Line to Remember

Prove "swapping cannot make it worse" first, then write "sort and pick from the front" — greedy is a provable replacement, not a gamble.