1103. As Many Tasks as the Bell Allows

You have T minutes before the bell. Task i takes t[i] minutes and cannot be interrupted or shared. You may do the tasks in any order and skip whichever you like.

Print the largest NUMBER of tasks you can finish inside T minutes.

T = 10, tasks 5 3 8 1 2 -> 4 do 1, 2, 3 and then 5, using 11? no

That first line is deliberately left wrong so you check it. 1 + 2 + 3 + 5 = 11, which is past 10, so only 1 + 2 + 3 = 6 fits and the answer is 3. Here are three correct lines:

T = 10, tasks 5 3 8 1 2 -> 3 1 + 2 + 3 = 6 T = 7, tasks 7 7 7 7 -> 1 T = 0, tasks 0 0 5 -> 2 two tasks take no time at all

## What most people try first

Trying every subset. There are 2^n of them, and at n = 200000 there is no machine and no century that finishes.

The second instinct is to reach for a knapsack table, since "pick a subset within a budget" is the knapsack shape. It would work and it costs O(n * T), and with T as large as 10^15 there is no table to build. The reason a table is not needed here is that every task is worth the same: one. That is exactly the special case in which greedy beats dynamic programming.

## The method

sort t ascending used = 0 count = 0 for x in t: if used + x <= T: used = used + x count = count + 1 else: break

One sort and one pass, O(n log n).

The break is safe because the list is sorted: once a task does not fit, no later task fits either.

## Why the shortest tasks are the right ones

Suppose an optimal selection of m tasks is not the m shortest. Then it contains some task b while some shorter task a is left out. Swap b out and a in. The count is unchanged, and the total falls by t[b] - t[a], which is not negative, so the selection still fits inside T.

Repeating the swap turns any optimal selection of size m into the m shortest tasks without ever breaking the budget. So if any selection of size m fits, the m shortest fit, which is exactly what the greedy checks in increasing order of m.

Notice that this argument uses "every task is worth 1" twice: once to say the count is unchanged by the swap, and once to say we only care about the total time. Give the tasks different values and it collapses, which is problem #1039's territory.

## The boundary that breaks a careless implementation

Tasks of length 0 are allowed and always fit, even when T is 0. A solution that starts the loop at the first task strictly longer than 0, or that treats T = 0 as "nothing can be done", answers 0 on T = 0, tasks 0 0 5 where 2 is right.

The test is used + x <= T, with <=. A task that exactly exhausts the remaining time fits.

## Sizes

T reaches 10^15 and a single task reaches 10^9, so both the budget and the running total need 64 bits. 10^15 is far past the 2147483647 limit of a signed 32-bit integer, and a 32-bit program cannot even read the budget of the largest test, let alone compare against it.

## A related problem

Problem #1102 also sorts these same durations ascending but asks for a sum rather than a count, and there every task must be done. The shared move is "shortest first"; what differs is the quantity the exchange argument protects.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ T ≤ 1000000000000000` - `0 ≤ t[i] ≤ 1000000000`