How can we solve Activity Selection Problem with reserve activities?

Let’s say we have chosen some set u of non-overlapping activities. Now, for every u_i activity, we need to choose reserve activity that is not present in set u, and is overlapping with at most one activity from u, which is u_i.

Any reserve activity can overlap with other reserve activities, as long as it overlaps with at most u_i activity. Reserve activities can be shared among multiple activities from set u.

My approach to solve this problem is following:

1. Solve basic activty selection problem, so we have set u of length k.
2. We can observe that if we choose k-th activity from set u, remove it from set u and use it as reserve activity for all activities in set u, then answer to our problem will be k - 1.
3. Because k is the length of longest possible set of non-overlapping activities, we can improve our answer from k - 1 to k. I’m not sure, but I think it’s possible only when for every activity from set u we can assign different reserve activity.

That’s my code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

bool comp(pair<pair<int, int>, int> const &l, pair<pair<int, int>, int> 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<pair<pair<int, int>, int>> 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<pair<pair<int, int>, int>> primary_activities;
    primary_activities.reserve(n);
    vector<bool> 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<int> 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 <= r)
            {
                reserve_activities.push_back(activities[j].second);
                break;
            }
        }
    }

    if (reserve_activities.size() == k)
    {
        cout << k << 'n';
        for (int i = 0; i < k; ++i)
        {
            cout << (primary_activities[i].second + 1) << ' ' << (reserve_activities[i] + 1) << 'n';
        }
    }
    else
    {
        cout << k - 1 << 'n';
        for (int i = 0; i < k - 1; ++i)
        {
            cout << (primary_activities[i].second + 1) << ' ' << (primary_activities.back().second + 1) << 'n';
        }
    }
}

Firstly, I read input: n (number of given activities), then n lines constisting of activities duration described by range [l, r].

My u set is represented by primary_activities. Here are activities chosen while solving base activity selection problem. Then, for every primary_activities[i], I search for reserve activity such that it starts after previous primary activity (primary_activities[i-1]) ends and such that it ends before next priary activity (primary_activities[i+1]) starts.

In output, I print the k = max length of found set, and then k lines consisting of pairs {primary activity, reserve activity assigned to it} .

I can’t find out what’s wrong with my logic. This code doesn’t pass many testcases, because it often gives too small answer (k-1 instead of k), and of course is too slow.

I believe there must be something like O(NlogN) solution. So how to solve this problem?

Problem statement is from XXXI Polish Olympiad in Informatics, link to original problem statement in Polish