algorithm

gistfile1.md

计算一组Range所覆盖的不重复整数的个数，求 < O(n*n) 的算法。

def cover(rs: Range*):Int = ???


assert(cover(0 to 4, 1 to 5) == 6)
assert(cover(0 to 4, 1 to 3) == 5)
assert(cover(0 to 4, 6 to 7) == 7)
assert(cover(0 to 4, 6 to 7, 2 to 6) == 8)

Based on @ChenLingPeng 's algorithm, but more idiomatic scala:

def cover(rs: Range*): Int = {
  @annotation.tailrec
  def helper(xs: List[Range], accu: Int):Int = xs match {
    case Nil => accu
    case r :: Nil => accu + r.size
    case r1 :: r2 :: tail => 
      val nextAccu = accu + r1.size
      if (r2.head > r1.last) helper(r2 :: tail, nextAccu)
      else if (r2.last > r1.last) helper(((r1.last + 1) to r2.last) :: tail, nextAccu)
      else helper(r1 :: tail, accu)
  }
  helper(rs.sortBy(_.start).toList, 0)
}

def cover(r: Range*) = r.foldLeft(Set[Int]())(_ ++ _).size

@songfei1983 🆒 ❗

cool !