Define a partial order on the ranges by the comparator . Then, we want to find the size of the maximum antichain in this partial order. By Dilworth’s theorem, this is equivalent to the size of the minimum chain cover. For instance, if our ranges are , the maximum antichain is , and the minimum chain cover is .
We can find the minimum chain cover via a simple greedy algorithm. Let’s say we’ve found a covering of the first elements. Then, the -th element can either be added to the end of an existing chain or placed into a new one. Simulating this process with a set corresponds exactly to the solution described in the editorial.