Задача о выборе заявок — это классическая оптимизационная задача, решаемая жадным алгоритмом. Суть сводится к тому, чтобы из списка заявок с указанием времени начала и окончания выбрать как можно больше непересекающихся по времени объектов. Жадный подход позволяет эффективно получить оптимальный ответ без полного перебора всех вариантов.
Предстоит выбор из набора мероприятий, у каждого из которых есть время начала l и время окончания r. Необходимо подобрать максимально возможное число таких событий так, чтобы они не пересекались во времени. При этом алгоритм должен находить оптимальный набор без полного перебора всех вариантов.
Цель задачи — выбрать как можно больше мероприятий без их пересечения, где каждое мероприятие задано временем начала и окончания. В жадном подходе на каждом шаге делается наилучший выбор, что в итоге приводит к оптимальному решению в целом.
Сначала все мероприятия сортируются по времени окончания. Первым всегда берётся то, которое заканчивается раньше остальных. Затем для каждого последующего мероприятия проверяется, начинается ли оно не раньше момента окончания последнего выбранного: если да — оно включается в решение. Такой порядок гарантирует отсутствие накладок.
Главная идея жадного метода — на каждом шаге отдавать предпочтение мероприятию с наименьшим временем окончания, чтобы максимально «освободить» пространство для последующих мероприятий. Это позволяет получить наибольшее возможное количество выбранных событий.
struct activity {
int l;
int r;
};
bool compare(const activity &a, const activity &b) {
return a.r < b.r;
}
vector<activity> solveActivitySelectionProblem(vector<activity> &activities) {
if (activities.size() <= 1)
return activities;
// Сортируем заявки так, чтобы первой шла та, которая завершается раньше всего.
sort(activities.begin(), activities.end(), compare);
// Контейнер для выбранных непересекающихся заявок.
vector<activity> selected_activities;
// Всегда выбираем первую (самую раннюю по окончанию) заявку.
selected_activities.push_back(activities[0]);
// Отслеживаем время окончания последней выбранной заявки.
int last_finish_time = activities[0].r;
for (size_t i = 1; i < activities.size(); ++i) {
// Если следующая заявка начинается в или после времени окончания последней выбранной, выбираем её.
if (activities[i].l >= last_finish_time) {
selected_activities.push_back(activities[i]);
last_finish_time = activities[i].r;
}
}
return selected_activities;
}
class Activity {
int l;
int r;
public Activity(int l, int r) {
this.l = l;
this.r = r;
}
}
public class ActivitySelection {
public static Comparator<Activity> compareByFinishTime = new Comparator<Activity>() {
@Override
public int compare(Activity a, Activity b) {
return Integer.compare(a.r, b.r);
}
};
public static List<Activity> solveActivitySelectionProblem(List<Activity> activities) {
if (activities.size() <= 1)
return activities;
// Сортируем заявки так, чтобы первой шла та, которая завершается раньше всего.
Collections.sort(activities, compareByFinishTime);
List<Activity> selectedActivities = new ArrayList<>();
selectedActivities.add(activities.get(0));
int lastFinishTime = activities.get(0).r;
for (int i = 1; i < activities.size(); i++) {
// Если следующая заявка начинается в или после времени окончания последней выбранной, выбираем её.
if (activities.get(i).l >= lastFinishTime) {
selectedActivities.add(activities.get(i));
lastFinishTime = activities.get(i).r;
}
}
return selectedActivities;
}
}
class Activity:
def __init__(self, l, r):
self.l = l
self.r = r
def solve_activity_selection_problem(activities):
if len(activities) <= 1:
return activities
# Сортируем заявки так, чтобы первой шла та, которая завершается раньше всего.
activities.sort(key=lambda activity: activity.r)
selected_activities = []
selected_activities.append(activities[0])
last_finish_time = activities[0].r
for i in range(1, len(activities)):
# Если следующая заявка начинается в или после времени окончания последней выбранной, выбираем её.
if activities[i].l >= last_finish_time:
selected_activities.append(activities[i])
last_finish_time = activities[i].r
return selected_activities
Сортировка списка из n мероприятий выполняется за $O(n \log n)$, а сам отбор, проходя по уже упорядоченному массиву, занимает $O(n)$. В итоге суммарная временная сложность остаётся $O(n \log n)$, причём именно этап сортировки оказывает наибольшее влияние.