Note that a <= b, b <= a creates an equivalence class. Note also a < b, b <= a creates an inconsistency and no ordering of equivalence classes is possible. Consider a <= c, b <= c, a < d, b <= d as a good case with which to start designing an algorithm.

If it helps, visualise the system as a marble maze such that (a, b) means the marble can travel from a to b, and if a < b, then the traverse is downhill. Is the maze consistent (not an Escher), what is the total depth of the maze, and which nodes are at which levels?

This is an instruction scheduling problem for a compiler, the solution probably requires a topological sort on the transitive closures over <= of elements reachable from one end of a < relation. I have not yet had the clarity of thought required to solve it, but it seems almost immediate that a good solution should take at most O(n^2) time.

## Error

Your reply will be screened

Your IP address will be recorded

You must follow the Privacy Policy and Google Terms of use.