Техник и приборы
От: kfmn Россия  
Дата: 13.11.18 07:33
Оценка:
Всем привет!

Нужна подсказка в такой задаче:

Есть N приборов, пронумерованных от 1 до N, для каждого известно время подготовки к работе (Ai) и работы до отключения (Bi). И есть техник, который может подготовить любой прибор к работе и включить, после чего тот отработает свое время и отключится. Готовить к работе техник может в каждый момент времени только один прибор, но если какой-то прибор не работает в данный момент, техник не имеет права отдыхать.
Когда все приборы работают, он может, наконец, отдохнуть, пока какой-то прибор не отключился.

Требуется, зная Ai и Bi (целые количества минут), сказать, в каком порядке следует включать приборы, чтобы иметь возможность хоть немного отдохнуть, либо сказать, что это невозможно.

Скорее всего, что-то очень простое, но в голову ничего разумного пока не пришло...
Отсортировать по убыванию Bi — не годится. Например: (Ai, Bi) = (1, 5), (4, 3), (1, 1). В таком порядке отдохнуть не получится, но если сначала подготовить и включить второй, а потом первый и третий, то останется 1 минута на отдых.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.