Skyline.scala

import scala.annotation.tailrec

case class B(l: Int, h: Int, r: Int)

case object B {
  val buildings = List(B(1, 11, 5), B(2, 6, 7), B(3, 13, 9), B(12, 7, 16), B(14, 3, 25), B(19, 18, 22), B(23, 13, 29), B(24, 4, 28))
}

object Skyline extends App {
  val edges = B.buildings.map(b=>Seq(b.l,b.r)).flatten.toSet.toSeq.sorted
  val ac = for {
    Seq(l,r) <- edges.sliding(2)
    active = B.buildings.filter(b=> l >= b.l && b.r >= r)
    h = (0 :: active.map(_.h)).max
  } yield ((l,r), h, (r-l)*h)
  println(ac.mkString("\n"))
}

object SkylineImproved extends App {
  def merge(bs: List[B]): List[B] = {
    @tailrec def rec(bs: List[B], acc: List[B]): List[B] = bs match {
      case a :: Nil                                   => a :: acc
      case a :: b :: tail if a.r <  b.l               => rec(b                     :: tail, B(a.r, 0  , b.l) :: a :: acc)
      case a :: b :: tail if a.r == b.l               => rec(b                     :: tail,                     a :: acc)
      case a :: b :: tail if a.r <= b.r && a.h == b.h => rec(     B(a.l, a.h, b.r) :: tail,                          acc)
      case a :: b :: tail if a.r <= b.r && a.h <  b.h => rec(b                     :: tail, B(a.l, a.h, b.l)      :: acc)
      case a :: b :: tail if a.r <= b.r && a.h >  b.h => rec(a :: B(a.r, b.h, b.r) :: tail,                          acc)
      case a :: b :: tail if a.r >  b.r && a.h >= b.h => rec(a                     :: tail,                          acc)
      case a :: b :: tail if a.r >  b.r && a.h <  b.h => rec(b :: B(b.r, a.h, a.r) :: tail, B(a.l, a.h, b.l)      :: acc)
    }
    rec(bs, Nil).reverse
  }
  val result = merge(B.buildings)
  println(result.mkString(","))
  println("B(1,11,5),B(5,6,3),B(3,13,9),B(9,0,12),B(12,7,16),B(16,3,19),B(19,18,22),B(22,3,23),B(23,13,29)")
}

SkylineJS.scala

import scala.annotation.tailrec

case class B(l: Int, h: Int, r: Int, c: Symbol = 'W)

object ScalaJSExample extends js.JSApp{
  val colors = Stream.continually(Array('R, 'Y, 'G, 'C, 'B, 'M).toStream).flatten
  val buildings = List(B(1, 11, 5), B(2, 6, 7), B(3, 13, 9), B(12, 7, 16), B(14, 3, 25), B(19, 18, 22), B(23, 13, 29), B(24, 4, 28), B(30, 4, 50), B(32, 6, 48), B(34, 8, 46), B(36, 10, 44)).zip(colors).map{ case (b,cn)=>b.copy(c=cn)}
  def merge(bs: List[B]): List[B] = {
    @tailrec def rec(bs: List[B], acc: List[B]): List[B] = bs match {
      case a :: Nil                                                 => a :: acc
      case a :: b :: tail if a.r <  b.l                             => rec(b                                      :: tail, B(a.r, 0  , b.l) :: a :: acc)
      case a :: b :: tail if a.r == b.l                             => rec(b                                      :: tail,                     a :: acc)
      case a :: b :: tail if a.r <= b.r && a.h == b.h               => rec(                      B(a.l, a.h, b.r) :: tail,                          acc)
      case a :: b :: tail if a.r <= b.r && a.h <  b.h && a.l == b.l => rec(b                                      :: tail,                          acc)
      case a :: b :: tail if a.r <= b.r && a.h <  b.h               => rec(b                                      :: tail, B(a.l, a.h, b.l)      :: acc)
      case a :: b :: tail if a.r <  b.r && a.h >  b.h               => rec(a :: insert(B(a.r, b.h, b.r), tail)(_.l < _.l),                          acc)
      case a :: b :: tail if a.r == b.r && a.h >  b.h               => rec(a                                      :: tail,                          acc)
      case a :: b :: tail if a.r >  b.r && a.h >= b.h               => rec(a                                      :: tail,                          acc)
      case a :: b :: tail if a.r >  b.r && a.h <  b.h && a.l == b.l => rec(b :: insert(B(b.r, a.h, a.r), tail)(_.l < _.l),                          acc)
      case a :: b :: tail if a.r >  b.r && a.h <  b.h               => rec(b :: insert(B(b.r, a.h, a.r), tail)(_.l < _.l), B(a.l, a.h, b.l)      :: acc)
    }
    rec(bs, Nil).reverse
  }

  def insert[A](i: A, l: List[A])(p: (A,A) => Boolean): List[A] ={
    if (l.isEmpty) i :: l
    else if (p(l.head,i)) l.head :: insert(i, l.tail)(p)
    else i :: l
  }
  
  def randomBuildings(n: Int, mw: Int, mh: Int) = {
    import scala.util.Random.nextInt
    val ls = Stream.continually(nextInt % 3 + 3).take(n).foldLeft(List(1))((z, i)=> (i+z.head) :: z).reverse
    ls.map{
      l=>
      val w = nextInt % 10 + 11
      val h = (nextInt % 10 + 11) / (w / 3) + 1
      B(l, h, l + w)
    }
  }

  def main(): Unit = {
    val result = merge(buildings)
    println(buildings.mkString(","))
    println(result.mkString(","))
    
    val randBuildings = randomBuildings(100, 20, 20).zip(colors).map{ case (b,cn)=>b.copy(c=cn) }
    lazy val randResult = merge(randBuildings)
    
    

    val (h, w) = (Page.canvas.height, Page.canvas.width)
    
    Page.renderer.clearRect(0, 0, w, h)

    for {
      (b: List[B], offset: Int) <- List(buildings, result, randBuildings, randResult).zip(150 to 1000 by 100)
      B(l,h,r,c) <- b
      color: String = c match {
        case 'R => "red"
        case 'Y => "yellow"
        case 'G => "green"
        case 'C => "cyan"
        case 'B => "blue"
        case 'M => "magenta"
        case 'W => "white"
      }
    } {
      Page.renderer.strokeStyle = color
      Page.renderer.strokeRect(l*4, offset - h*4, (r-l)*4, h*4)
    }
  }
}