probably the most common example of a problem with a simple greedy solution is the following:

You have a set of intervals, and want to choose a maximal pairwise disjoint set of intervals.

A pretty similar related problem is

You have a set of intervals, and want to draw a minimal number of lines perpendicular to the segments to stab them all.

These problems both have very straightforward solutions.

For the maximal set of intervals one, repeatedly take the interval that ends first, and then cross out intervals that overlap with that interval.

Similarly for the stab version, repeatedly stab at the first endpoint, and remove things that got stabbed.

ok, now here is a twist:

what if the intervals, rather than being situated in \(\mathbb{R}\) are situated in the circle \(\mathbb{R}/ \mathbb{Z}\)?

Now, there is no clear starting point. So it seems kind of tough. However, the problem still admits a \(n\log n\) solution!

We will focus on the stabby version, but the other version is quite analogous.

0. Trivial \(+1\) approximation.
1. Trivial \(n^2\) solution
2. First we do some preprocessing, destroy proper containments
3. Now we iterate in a circle and compute the greedy successors
4. Now we look at the greedy successor cycle-y things

yay

TODO: later, actually write this up well

TODO: what if we have weights? Can we do DP in the circle case?