|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
25.05.2009, 11:42 | #1 |
Пользователь
Регистрация: 12.01.2009
Сообщений: 19
|
Помогите пожалуйста с задачей..
Известна так же как Задача о выборе заявок...
Пусть подано N заявок на прове- дение занятий в одной и той же ау- дитории. Для каждого занятия из- вестно время его проведения [bi,ei], где bi — время начала заня- тия, еi — время окончания. Два раз- ных занятия не могут перекры- ваться по времени, но условимся, что начало одного может совпа- дать с окончанием другого. Зада- ча состоит в том, чтобы выбрать максимальное число совместимых по времени занятий. Пожалуйста... помогите с ней... P.S есть алгоритм...(но применить не могу.) |
25.05.2009, 12:01 | #2 |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,792
|
Думаю тут нужно просто сортировать занятия по времени, а потом просто брать с того конца где начинаются занятия с меньшим временем из отсортированного списка.
I'm learning to live...
|
25.05.2009, 12:22 | #3 | |
Пользователь
Регистрация: 12.01.2009
Сообщений: 19
|
Цитата:
тут идет реализация жадного алгоритма... Код:
|
|
25.05.2009, 12:28 | #4 | |
Форумчанин
Регистрация: 07.04.2009
Сообщений: 245
|
Задача сформулирована ужасно. Если не ограничить время "работы" аудитории, то тогда всегда можно провести все занятия и их очерёдность на имеет смысла. А если время "работы" ацдитории ограничено, то как поступать с остатком времени, в течении которого она будет простаивать? Возможно ого необходимо оптимизировать? И что значит
Цитата:
Всякое безобразие должно быть единообразным. Тогда это называется порядком.
|
|
25.05.2009, 12:36 | #5 |
Пользователь
Регистрация: 12.01.2009
Сообщений: 19
|
Даны n заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия (si и fi для i-й заявки). В случае пересечения заявок можно удовлетворить лишь одну из них. Заявки с номерами i и j совместны, если интервалы [si,fi) и [sj,fj) не пересекаются (то есть f_i \le s_j или f_j \le s_i). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.
С википедии взял... Последний раз редактировалось Dezolyator; 25.05.2009 в 12:38. |
25.05.2009, 13:12 | #6 |
Форумчанин
Регистрация: 07.04.2009
Сообщений: 245
|
Если сделать геометрическую интерпретацию, то задачу можно сформулировать следующим образом:
Из заданого множества найти максимальное количество интервалов времени, проекции которых на временную ось не пересекаются. Я правильно понял задачу?
Всякое безобразие должно быть единообразным. Тогда это называется порядком.
Последний раз редактировалось Anatole; 25.05.2009 в 13:14. Причина: синтаксическая ошибка |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Помогите пожалуйста с задачей | Ronk | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 19.01.2009 04:50 |
Помогите пожалуйста с задачей. | Kold | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 12.12.2008 20:20 |
Помогите с задачей пожалуйста | Apache | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 07.10.2008 20:35 |
Пожалуйста, помогите с задачей по C++ | Maksimym | Помощь студентам | 2 | 10.01.2008 23:18 |
помогите пожалуйста с задачей! | Coolmanz | Помощь студентам | 2 | 06.01.2008 23:07 |