1. Идея

Нужно выбрать как можно больше задач, уложившись в суммарное время T.

Если цель — максимизировать именно количество задач, то выгодно брать самые короткие задачи. Каждая такая задача тратит меньше времени и оставляет больше запаса на следующие.

Значит, естественная стратегия такая:

• отсортировать все времена t_i по возрастанию;
• идти слева направо;
• пока очередную задачу еще можно добавить, добавляем её;
• как только уже нельзя, дальше смысла смотреть нет.

2. Наблюдения

Наблюдение 1

Порядок решения можно выбирать произвольно. Значит, исходный порядок задач во входных данных не важен.

Наблюдение 2

Чтобы решить как можно больше задач, надо в первую очередь рассматривать задачи с минимальным временем.

Например, если есть задачи на 1, 2, 3, 10 минут, то набор из коротких задач почти всегда позволяет взять больше элементов, чем набор с длинными.

Наблюдение 3

После сортировки, если мы не можем взять задачу с номером i, то никакую следующую тоже не сможем взять, потому что дальше времена только больше или равны.

То есть после первого не влезает можно сразу остановиться.

3. Алгоритм

1. Считать n, T и массив t.
2. Отсортировать массив t по возрастанию.
3. Завести:
   • sum — уже потраченное время;
   • answer — количество выбранных задач.
4. Перебрать задачи в отсортированном порядке:
   • если sum + t[i] <= T, то:
     • прибавить t[i] к sum;
     • увеличить answer;
   • иначе остановиться.
5. Вывести answer.

4. Почему это работает

Докажем, почему жадный выбор самых коротких задач дает оптимальный ответ.

Рассмотрим любое число k. Чтобы успеть решить k задач, нужно выбрать какие-то k времен, сумма которых не превосходит T.

Но среди всех наборов из k задач минимальную возможную сумму дают именно k самых маленьких элементов массива. Это очевидно: если в наборе есть более длинная задача вместо более короткой, такую замену можно сделать и сумма не увеличится.

Значит:

• если сумма k самых коротких задач не превышает T, то решить k задач возможно;
• если даже сумма k самых коротких задач больше T, то никакие другие k задач тоже не подойдут.

Следовательно, максимальное число задач — это наибольшее k, для которого сумма первых k элементов после сортировки не превосходит T.

Именно это и делает алгоритм: он идет по отсортированному массиву и считает, сколько первых минимальных времен помещается в лимит.

5. Сложность

Основное время тратится на сортировку:

• сортировка: O(n log n)
• проход по массиву: O(n)

Итоговая сложность: O(n log n).

По памяти:

• хранится массив из n чисел, то есть O(n).

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    long long T;
    cin >> n >> T;

    vector<long long> t(n);
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    sort(t.begin(), t.end());

    long long sum = 0;
    int answer = 0;

    for (int i = 0; i < n; i++) {
        if (sum + t[i] <= T) {
            sum += t[i];
            answer++;
        } else {
            break;
        }
    }

    cout << answer << '\n';
    return 0;
}

7. Код на Python 3

n, T = map(int, input().split())
t = list(map(int, input().split()))

t.sort()

total = 0
answer = 0

for x in t:
    if total + x <= T:
        total += x
        answer += 1
    else:
        break

print(answer)