§ A slew of order theoretic and graph theoretic results

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
Naively, the solution goes as follows, which can be tested against CSES' movie festival question
// https://cses.fi/problemset/task/1629
int 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 jobin 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), henceend(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 thesame length between O~, O and O*.