Хорошо, я не собираюсь отвечать на этот вопрос правильным кодом, и, самое большее, у меня будет псевдокод, когда я попытаюсь определить, что я понимаю в проблеме. Я также сделаю предположение, что вы будете использовать целочисленные значения времени, а не числа с плавающей запятой, хотя я уверен, что в конце дня это не будет иметь большого значения.
Жадное решение - просто назначить бесплатный лекционный зал и всегда использовать лекционные залы, которые использовались ранее. То есть я совершенно уверен, что решение просит вас сделать.
Итак, во-первых, я бы создал какой-то struct или class, который содержит все «события», где мы определяем «событие» как время начала или окончания действия. Это struct / class также будет содержать ссылку на то, какое действие было временем начала / окончания.
Может быть, вроде как (синтаксис C ++, потому что это проще и я ленивый):
struct evt
{
int activityID;
int time;
bool isStart;
};
Следующим шагом будет создание экземпляра этого struct или class для времени начала / окончания каждого действия, а затем помещение его в некую структуру данных списка (если бы это был C ++, я бы использовал vector, и я предполагаю ArrayList для Java), а затем сортирует события, основанные на их time. Итак, для Java вам понадобится какая-то функция сравнения, которая определяет порядок этих событий в зависимости от их времени. Кроме того, в вашем компараторе событие, которое является начальным событием, будет идти позже, чем событие, которое является завершающим событием (помните, интервалы полуоткрыты). Я позвоню ArrayList "eventList".
Далее у вас есть два списка, которые я бы назвал n залами (вам потребуется максимум n залов для выполнения всех действий). В одном списке есть все залы. Это список залов, которые не используются. Другой список пуст. Это будет список залов, которые используются. Это могут быть списки, которые можно удалить с лицевой стороны (я думаю, что Java ArrayList может сделать это).
У вас был бы какой-то способ идентификации зала, и, возможно, какой-то справочный массив, чтобы каждое мероприятие можно было назначить для зала. Эта часть немного неясна, и я бы лучше оставил вам детали реализации, но если бы n не было слишком большим, я бы, вероятно, (опять же с C ++) имел vector<int> размера n , а i -й элемент в этом vector будет идентификатором зала или -1, если он еще не был назначен. И если бы я пробовал это на Java, это был бы массив int[n].
Затем я перебирал бы eventList, и на каждом событии я проверял, было ли это время окончания или время начала. Если это время начала, я бы взял передний элемент списка «свободных залов» и поместил его в «используемые» залы. Если бы это было время окончания, я бы взял только что законченный зал, удалил его из списка «в использовании» и поместил обратно в начало списка «свободных залов». Помните, вам также нужно обновить массив ссылок, о котором я говорил ранее.
Наконец, немного повозившись, вы смогли найти, сколько залов было использовано. Линейного прохода через массив или счетчик, который работал, когда вы использовали залы, было бы достаточно. Один из способов, который, на мой взгляд, работает, состоит в том, чтобы записать максимальный размер списка, который содержит количество используемых залов за один раз, хотя это может быть неверно (не проверил его полностью).
Я просто делаю это изо всех сил, так что это решение, вероятно, немного сбивает с толку в данный момент. Извини за это. Я постараюсь обобщить это здесь:
- Объявите класс, который суммирует время начала / окончания как события
- Сортировка всех начальных и конечных времен в массиве, причем более ранние времена идут раньше в списке, а конечные времена появляются раньше начальных
- Составьте список залов и еще один (пустой список), который будет использовать все залы
- Обработайте каждое событие, переместив зал в список использования, если это время начала, и в список свободных, если это время окончания
Поскольку это довольно длинный пост, иЯ не предоставил много кода (я пытался пропустить подсказки, но я не знаю, был ли он полезен), пожалуйста, дайте мне знать, если у вас есть дополнительные вопросы, и я постараюсь помочь как можно лучше.
Проблема «выбора деятельности», как видно здесь , может быть решена жадным способом, всегда выбирая действия, которые заканчиваются раньше.Я думаю, что это немного по-другому, но я просто включил его, потому что это может быть интересно.