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)

object RangeCount extends App{
  def cover(rs: Range*) = {

    rs.foreach{r=>
      if(r.head>r.last || r.step != 1) throw new Exception(s"illegal range $r")
    }

    val min = rs.foldLeft(Int.MaxValue){(a,b)=>
      Math.min(a,b.head)
    }-1
    rs.sortBy(_.head).foldLeft((min,0)){
      (res,range) =>
        val end = res._1
        val add = range match {
          case r if r.head>end => (r.size, r.last)
          case r if r.head<=end && r.last > end => (r.last-end,r.last)
          case _ => (0,end)
        }
        (add._2, add._1+res._2)
    }._2
  }
  println(cover(0 to 4, 1 to 5))
  println(cover(0 to 4, 1 to 3))
  println(cover(0 to 4, 6 to 7))
  println(cover(0 to 4, 7 to 8,8 to 8, 2 to 6, 3 to 1 by -1))
}

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 !