Интересная задачка

[heart_beater]

Только что по рабочей необходимости пришлось решать оригинальную задачку. Речь шла об объединении секторов на радарной развёртке, но чтобы не объяснять, что это такое, приведу более "бытовой" аналог :)

Дано: Первый человек встаёт в B1 часов и ложится спать в E1 часов. Второй человек встаёт в B2 часов и ложится спать в E2 часов.
Найти:

Comments

[heart_beater]

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

[heart_beater]

Да, минимальный. Мне-то надо было решить именно для двух, про N я не думал (хотя, алгоритм, понятное дело, использует эту функцию много раз и где-то может косвенно объединить и N). А почему не сводится?

[anjutka]

Это задачка из серии "у стола отпилили угол, сколько углов осталось":)?
Я вот 20 минут пыталась понять "простоту" условия - какой такой минимальный сектор, когда такой сектор всего один (или весь круг)? Потом поняла, что видимо имеются в виду сектора, образованные границами сна/бодрствования.

[heart_beater]

Просто в каждом конкретном случае задача получается вообще как для 1-го (ну, может 2-го или 3-го) класса, а вот в общем виде все сложнее :) Сектор - это на развертке, а в случае со сном его аналогом будет сектор на циферблате часов (с оговоркой на то что в сутках не 12, а 24 часа). А минимальный - потому что решений может быть 2, в этом случае более интересен более короткий сектор / интервал.

[anjutka]

Ты с кем сейчас разговариваешь:))?
Я намекаю, что задача сформулирована не очень корректно. Потому что "промежуток времени когда хотя бы один из них не спит" - всего один! или все сутки, если время сна у обоих не пересекается.

[heart_beater]

В том-то и дело, что нет!
Пример: один спит с 0 до 18, второй - с 12 до 6 утра (неправдоподобно, конечно, но условию не противоречит :)). В этом случае будет 2 одинаковых промежутка, удовлетворяющих условию - с 6 до 12 утра и с 18 до 0.