如何用PartialOrdering排序一个集合

Question

我需要订购一套信封。每个信封的高度和宽度都有说明。如果可以插入到信封e2中，则信封e1小于信封e2。如果信封e1不能插入信封e2，反之亦然，则它们不能进行比较。

我如何在scala中订购这些信封?我在网上找不到关于那件事的任何信息。

下面是我的一些代码:

object EnvelopeOrdering extends PartialOrdering[(Int, Int)] {
  override def tryCompare(x: (Int, Int), y: (Int, Int)): Option[Int] = {
    if (x._1 < y._1 && x._2 < y._2) return Some(1)
    if (x._1 > y._1 && x._2 > y._2) return Some(-1)
    if (x._1 == y._1 && x._2 == y._2) return Some(0)
    None
  }
  override def lteq(x: (Int, Int), y: (Int, Int)): Boolean = x._1 < y._1 && x._2 < y._2
}

Answer 1

你感兴趣的是拓扑排序，有一个经典的算法来执行它，复杂度按边数的顺序排列。在你的例子中，当且仅当第一个信封较小时，你将在两个信封之间有一个边缘(并且边缘应该从较小的信封指向较大的信封)。