Как называется такая задача?

Question

[EgoRedMC]

Более чем уверен, что такая задача существует, быть может даже в обобщенном виде. Подскажите пожалуйста, как она называется.
Задача звучит так:
Необходимо составить программу просмотра телепередач.
Каждая телепередача имеет следующие поля:
время начала, время окончания, номер, приоритет.
Нужно, чтобы в каждый момент времени смотрелась самая приоритетная телепередача.

Comments

[xmoonlight]

Нерешаемая или некорректная.

[Immortal_pony]

Обоснуйте

[xmoonlight]

Immortal_pony,

Каждая телепередача имеет следующие поля:
время начала, время окончания, номер, приоритет.

чтобы в каждый момент времени смотрелась самая приоритетная телепередача.

Приоритеты у всех разные или нет?
В каждый момент времени смотрелась самая приоритетная из всех, из всех на канале, из оставшегося числа всех, из оставшегося числа на канале?
Море вопросов)

[Alexej Simakov]

Проблема с предпочтениями, допустим даже они строгого порядка, как мне видится вот в чем. Что делать если приоритетная передача заканчивается позже чем начинается другая более приоритетная передача. Досматривать до конца? Бросать недосмотренной? Т.е. нужно определить набор правил по которым будут разрешаться ситуации с конфликтами предпочтений. И тут никакой учебник не поможет, их надо будет придумать самому для своей ситуации.

[xmoonlight]

Alexej Simakov, Точно! О чём я и говорю, что дали коня в вакууме)

Answer 1

[Codebaker]

Вам стоит почитать про задачи, которые решает теория расписаний.

Answer 2

[Mercury13]

Если считать, что любую передачу можно смотреть только целиком — это будет задача о заявках (=activity-selection problem).
Решается жадным алгоритмом в таком виде. Берутся самые приоритетные передачи и решается классическая задача о заявках: берём ту, которая кончается раньше всех, затем ту, которая кончается раньше всех и не противоречит имеющейся… В «окна» тем же алгоритмом вставляют менее приоритетные, и т.д.

Если считать, что можно бросать недосмотренные передачи — всё просто. При наступлении более приоритетной передачи переключаемся на неё.

Answer 3

[Сергей Соколов]

Не знаю, как называется такая задача.

Решается сортировкой времени событий и их перебором: в каждый такой момент надо принять решение "остаться / переключиться".

Есть приоритет текущей передачи (если она ещё не заканчивается). И есть приоритеты других передач в этот момент (особенно интересуют начинающиеся).