CSES' movie festival question
```
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)`

, 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 thesame length between `O~`

, `O`

and `O*`

.

#### § Explanation 2: posets and interval orders