I've been trying to abstract out the activity selection problem from the lens of order theory. For this, I plan on studying the following theorems/algebraic structures:

• Intransitive indifference with unequal indifference intervals
• Mirsky's theorem
• Dilworth's theorem
• Gallai–Hasse–Roy–Vitaver theorem
• Dirac's theorem
• Ore's theorem
• Course on discrete math
• cs.stackexchange: Finding longest chain in poset in sub-quadratic time

Naively, the solution goes as follows, which can be tested against CSES' movie festival question

// https://cses.fi/problemset/task/1629int main() {    int n;    cin >> n;    vector<pair<int, int>> ms(n);    for (int i = 0; i < n; ++i) {        cin >> ms[i].first >> ms[i].second;    }    std::sort(ms.begin(), ms.end(), [](pair<int, int> p1, pair<int, int> p2) {        return (p1.second < p2.second) ||               (p1.second == p2.second && p1.first < p2.first);    });    int njobs = 0;    int cur_end = -1;    for (int i = 0; i < n; ++i) {        if (cur_end <= ms[i].first) {            cur_end = ms[i].second;            njobs++;        }    }    cout << njobs << "\n";    return 0;}

§ Explanation 1: exchange argument

• The idea is to pick jobs greedily , based on quickest finishing time .
• The argument of optimality is strategy stealing. Think of the first job in our ordering O versus the optimal ordering O*.
• If we both use the same job, ie, O[1] = O*[1], recurse into the second job.
• If we use different jobs then O[1] != O*[1].
• Since O[1] ends quickest [acc to our algorithm ], we will have that end(O[1]) < end(all other jobs), hence end(O[1]) < end(O*[1]).
• Since O* is a correct job schedule, we have that end(O*[1]) < start(O*[2]).
• Chaining inequalities, we get that end(O[1]) < end(O*[1]) < start(O*[2]).
• Thus, we can create O~ which has O~[1] = O[1] and O~[rest] = O*[rest]. ( ~ for "modified").
• Now recurse into O~ to continue aligning O* with O. We continue to have the same length between O~, O and O*.

§ Explanation 2: posets and interval orders