§ 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
• 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/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[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