Задача выбора активности с резервными операциями ⇐ C++

[Anonymous]

Как мы можем решить проблему выбора действий с помощью резервных действий?
Предположим, мы выбрали некоторый набор u непересекающихся действий. Теперь для каждого действия u_i нам нужно выбрать резервное действие, которого нет в наборе u и которое перекрывается не более чем с одним действием из u, то есть u_i. >.
Любая резервная деятельность может перекрываться с другими резервными действиями, если она перекрывается не более чем с деятельностью u_i. Резервные действия могут быть разделены между несколькими действиями из набора u.
Мой подход к решению этой проблемы следующий:

• Решите базовую задачу выбора действия, поэтому мы задали u длиной k.
• Мы можем наблюдать это, если выберем k-е code> активность из набора u, удалите ее из набора u и используйте в качестве резервной активности для всех действий в наборе u, тогда ответом на нашу задачу будет k - 1 >.
• Поскольку k — это длина максимально возможного набора непересекающихся действий, мы можем улучшить наш ответ с k - 1 до k. Я не уверен, но думаю, что это возможно только тогда, когда для каждого действия из набора u мы можем назначить разные резервные действия.

Это мой код:

Код: Выделить всё

#include [i]
#include 
#include 
#include 

using namespace std;

bool comp(pair
, int> const &l, pair const &r)
{
return l.first.second < r.first.second;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

int n;
cin >> n;

vector activities(n);
for (int i = 0; i < n; ++i)
{
cin >> activities[i].first.first >> activities[i].first.second;
activities[i].second = i;
}

sort(activities.begin(), activities.end(), comp);

int k = 0;
vector primary_activities;
primary_activities.reserve(n);
vector used(n);
int end = -1;
for (int i = 0; i < n; ++i)
{
if (activities[i].first.first >= end)
{
++k;
primary_activities.push_back(activities[i]);
end = activities[i].first.second;
used[activities[i].second] = true;
}
}

vector reserve_activities;
reserve_activities.reserve(k);

for (int i = 0; i < k; ++i)
{
int l = i - 1 >= 0 ? primary_activities[i - 1].first.second : INT_MIN;
int r = i + 1 < k ? primary_activities[i + 1].first.first : INT_MAX;
for (int j = 0; j < n; ++j)
{
if (!used[activities[j].second] && activities[j].first.first >= l && activities[j].first.second 

Подробнее здесь: [url]https://stackoverflow.com/questions/79020099/activity-selection-problem-with-reserve-activities[/url]