optimization of fence painting

PaintingFence.scala

import scala.util.control.TailCalls._

def solve(l: List[(Int, Int)]): Int = {
  def go(from: Int, to: Int, prevHeight: Int): TailRec[Int] = {
    val max = to - from
    val currHeight = l.slice(from, to).minBy(_._1)._1
    val hStrokes = currHeight - prevHeight
    // not sure it's legal, but in practice it seems that you always have only one item here
    val List(split) = l.slice(from, to).filter(_._1 - currHeight == 0).map(_._2)
    val indices: List[Int] = from :: split :: split + 1 :: to :: Nil
    val subLists = indices.grouped(2).filter(xs => xs.last - xs.head > 0)

    val trampolines = subLists.map(xs => tailcall(go(xs.head, xs.last, currHeight)))
    val sumTrampolines = trampolines.foldLeft(done(hStrokes))((b, a) => b.flatMap(bVal =>
      a.map(aVal => aVal + bVal)))
    sumTrampolines.flatMap(v => done(max).map(m => Math.min(m, v)))
  }
  go(from=0, to=l.size, prevHeight=0).result
}

val lst = (1 to 5000).toList.zipWithIndex
val res = solve(lst)

println(res)

// I've runned the code with `scala -savecompiled PaintingFence.scala` so compilation does not affect total running time