## § 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 job in our ordering O versus the optimal ordering O*.
• If we both use the same job, ie, O = O*, recurse into the second job.
• If we use different jobs then O != O*.
• Since O ends quickest [acc to our algorithm ], we will have that end(O) < end(all other jobs), hence end(O) < end(O*).
• Since O* is a correct job schedule, we have that end(O*) < start(O*).
• Chaining inequalities, we get that end(O) < end(O*) < start(O*).
• Thus, we can create O~ which has O~ = O 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*.