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.