如何使用PartialOrdering订购集合？

Question

我需要订购一系列信封.每个信封的高度和宽度都有描述.如果可以将信封插入信封2中,则信封1小于信封2.如果envelope1不能插入envelope2中,反之亦然,则无法比较它们.

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

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