Задача про тимлида и подарки

1 января 2026

Такие задачи часто встречаются на алгоритмических собеседованиях, поэтому наш вариант пригодится всем, кто готовится к техническим интервью.

Условие

В разгар предновогодней суеты тимлид Игорь решил порадовать коллег и купил для всех подарки. Но кто-то из сотрудников ушел в отпуск, кто-то уехал зимовать в теплые страны… В результате подарков получилось больше, чем коллег.

Чтобы разделить дары справедливо, Игорь решил следовать определенной логике. Каждого сотрудника записал табличку, а напротив вывел число — значение из массива ratings. Это число символизировало своеобразный итог года: кто сколько задач закрыл.

При этом тимлид установил строгие правила:

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

Задача

Дано n — количество сотрудников и массив случайных чисел — ratings, в котором указаны номера, полученные сотрудниками.

За оставшиеся до корпоратива часы определите минимальное количество подарков для всех сотрудников.

Пример 1:


      n = 3

ratings = [1,0,2]

Вывод: 5

Первому даем два подарка, второму — один, третьему — три.

Пример 2:


      n = 3

ratings = [9,9,9]

Вывод: 3

Всем сотрудникам раздаем по одному подарку.

Пример 3:


      n = 3

ratings = [1,2,2]

Вывод: 4

Первому даем один подарок, второму — два, третьему — один.

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

Решение

Задачу можно решить с помощью «жадного алгоритма» с двойным проходом, который имеет линейную сложность по времени и памяти O(n).

«Жадный алгоритм» с двойным проходом

Нам нужно сделать два прохода по массиву ratings:

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

Первый проход вернет нам массив RightToLeft[], второй проход — LeftToRight[]. Чтобы получить общее количество подарков, нужно сравнить элементы в обоих массивах и сложить максимальные значения.

Код на Python:


      import array
def get_min_candy(ratings):
#ratings — массив номеров сотрудников
n = len(ratings)
#массив для прохода слева направо, заполненный единицами
left_to_right_candy = array.array('i', [1] * n) 
#массив для прохода справа налево, заполненный единицами
right_to_left_candy = array.array('i', [1] * n)

#первый проход слева направо
for i in range(1, n):
#начинаем проход со второго элемента (i = 1) и сравниваем с числом слева
if ratings[i] > ratings[i - 1]:
#прибавляем один подарок
left_to_right_candy[i] = left_to_right_candy[i - 1] + 1

#второй проход справа налево
for i in range(n - 2, -1, -1):
	#начинаем проход со второго элемента с конца (i = n - 2)
if ratings[i] > ratings[i + 1]:
#прибавляем один подарок
right_to_left_candy[i] = right_to_left_candy[i + 1] + 1

    #считаем сумму и находим максимальное значение
    return sum(max(left_to_right_candy[i], right_to_left_candy[i]) for i in range(n))

if __name__ == "__main__":
arr = array.array('i', [2, 0, 3])
print(get_min_candy(arr))