§ 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: 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*.

§ Explanation 2: posets and interval orders