algorithm - 如何使用 PartialOrdering 订购收藏品？

Question

我需要订购一组信封。每个信封都用它的高度和宽度来描述。如果信封 1 可以插入信封 2，则信封 1 小于信封 2。如果信封1 无法插入信封2，反之亦然，则无法进行比较。

我如何在 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

您感兴趣的是拓扑排序，并且有一个经典算法可以按照边数的顺序以复杂度执行它。在您的情况下，当且仅当第一个信封较小时，您将在两个信封之间有一个边缘（并且边缘应该从较小的一个指向较大的一个）。