Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 25.05.2009, 11:42   #1
Dezolyator
Пользователь
 
Регистрация: 12.01.2009
Сообщений: 19
По умолчанию Помогите пожалуйста с задачей..

Известна так же как Задача о выборе заявок...

Пусть подано N заявок на прове-
дение занятий в одной и той же ау-
дитории. Для каждого занятия из-
вестно время его проведения
[bi,ei], где bi — время начала заня-
тия, еi — время окончания. Два раз-
ных занятия не могут перекры-
ваться по времени, но условимся,
что начало одного может совпа-
дать с окончанием другого. Зада-
ча состоит в том, чтобы выбрать
максимальное число совместимых
по времени занятий.

Пожалуйста... помогите с ней...
P.S есть алгоритм...(но применить не могу.)
Dezolyator вне форума Ответить с цитированием
Старый 25.05.2009, 12:01   #2
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Думаю тут нужно просто сортировать занятия по времени, а потом просто брать с того конца где начинаются занятия с меньшим временем из отсортированного списка.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 25.05.2009, 12:22   #3
Dezolyator
Пользователь
 
Регистрация: 12.01.2009
Сообщений: 19
По умолчанию

Цитата:
Думаю тут нужно просто сортировать занятия по времени, а потом просто брать с того конца где начинаются занятия с меньшим временем из отсортированного списка.
Посмотри на код пожалста:
тут идет реализация жадного алгоритма...

Код:
var
b,e: array[1..100] of integer;
{входные данные} 
a: set of byte; {искомое множество}
i,j,n: integer;

begin 
read(n);
for i:=1 to n do 
read(b[i],e[i]);
a := [1]; {начальное значение}
j := 1; {самый правый отрезок множества А - первый}

for i:=2 to n do 
if b[i]>=e[j] then begin
{если i-й отрезок лежит npaвee j-го}
a:=a+[i];
{то включаем j-й }
j := i; {и запоминаем его как самый правый в множестве А}

end;
for i:=1 to n do {выводим результат}
if (i in a) then writeln(i);
 end;
end.
Помоги доделать пожалста, если не трудно...
Dezolyator вне форума Ответить с цитированием
Старый 25.05.2009, 12:28   #4
Anatole
Форумчанин
 
Аватар для Anatole
 
Регистрация: 07.04.2009
Сообщений: 245
По умолчанию

Задача сформулирована ужасно. Если не ограничить время "работы" аудитории, то тогда всегда можно провести все занятия и их очерёдность на имеет смысла. А если время "работы" ацдитории ограничено, то как поступать с остатком времени, в течении которого она будет простаивать? Возможно ого необходимо оптимизировать? И что значит
Цитата:
выбрать
максимальное число совместимых
по времени занятий
.
Это что те занятия, которые поводятся в этой аудитории одновременно?
Всякое безобразие должно быть единообразным. Тогда это называется порядком.
Anatole вне форума Ответить с цитированием
Старый 25.05.2009, 12:36   #5
Dezolyator
Пользователь
 
Регистрация: 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.
Dezolyator вне форума Ответить с цитированием
Старый 25.05.2009, 13:12   #6
Anatole
Форумчанин
 
Аватар для Anatole
 
Регистрация: 07.04.2009
Сообщений: 245
По умолчанию

Если сделать геометрическую интерпретацию, то задачу можно сформулировать следующим образом:
Из заданого множества найти максимальное количество интервалов времени, проекции которых на временную ось не пересекаются.
Я правильно понял задачу?
Всякое безобразие должно быть единообразным. Тогда это называется порядком.

Последний раз редактировалось Anatole; 25.05.2009 в 13:14. Причина: синтаксическая ошибка
Anatole вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите пожалуйста с задачей 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