答案：時間帯重複チェック(応用編) - 一番良いアルゴリズムを頼む

best.scala

// お題：時間帯重複チェック(応用編)
// <http://d.hatena.ne.jp/fumokmm/20110329/1301403400>
// に対する、最良のアルゴリズムを考えた。 by @akihiro4chawon

/** 時刻; Time Point */
case class Point(hour: Int, minutes: Int) extends Ordered[Point] {
  def inMinutes = 60 * hour + minutes
  
  override def compare(that: Point) =
    this.inMinutes compare that.inMinutes
}
object Point {
  implicit def mkOrderingOps(p: Point) = implicitly[Ordering[Point]].mkOrderingOps(p)
}

/** 時間帯; Time Interval */
case class Interval(val beg: Point, val end: Point) extends Ordered[Interval] {
  
  override def compare(that: Interval) =
    (2 * (beg compare that.beg) + (end compare that.end)).signum
  
  def and(that: Interval): Option[Interval] = 
    Some(Interval(beg max that.beg, end min that.end)) filter {i => i.beg < i.end}
}
object Interval {
  def fromHoursMinutes(h1: Int, m1: Int, h2: Int, m2: Int) = 
    Interval(Point(h1, m1), Point(h2, m2))
}

object Test extends Application {
  type IntTuple4 = (Int, Int, Int, Int)
  
  def solve(ts: IntTuple4*) = {
    
    def overlaps(ts: List[Interval]): List[Interval] = ts match {
      case x1 :: x2 :: xs => x1 and x2 match {
        case Some(lap) => lap :: overlaps(Interval(lap.end, x1.end max x2.end) :: xs)
        case None => overlaps(x2 :: xs)
      }
      case _ => Nil
    }
    
    def merge(ts: List[Interval]): List[Interval] = ts match {
      case x1 :: x2 :: xs if (x1.end >= x2.beg) => merge(Interval(x1.beg, x2.end) :: xs)
      case x1 :: xs => x1 :: merge(xs)
      case Nil => Nil
    }
    
    // ここで、sorted にかかる計算量が O(NlogN) になる
//    merge(overlaps(ts.toList map (Interval.fromHoursMinutes _).tupled sorted))
    
    // 時刻の離散性に注目し、 bucket sort を使えばO(N)の計算量になる
    def bucketSort(ts: List[Interval]) = {
      val bucket = Array.fill(24 * 60)(List[Interval]())
      ts foreach {i => bucket(i.beg.inMinutes) ::= i}
      bucket.toList.flatten
    }
    merge(overlaps(bucketSort(ts.toList map (Interval.fromHoursMinutes _).tupled)))
  }
 
  for {arg <-Seq(
      // 例1(出力：(12, 0, 12, 15))
      Seq((12, 0, 13, 0), (10, 0, 12, 15)),
      // 例2(出力：(9, 0, 10, 30), (16, 0, 17, 0))
      Seq((16, 0, 23, 0), (9, 0, 17, 0), (5, 0, 10, 30)),
      // 例3(出力：(13, 0, 14, 0), (15, 0, 16, 0), (17, 0, 18, 0), (19, 0, 20, 0), (21, 0, 22, 0))
      Seq((12, 0, 23, 0), (13, 0, 14, 0), (15, 0, 16, 0), (17, 0, 18, 0), (19, 0, 20, 0), (21, 0, 22, 0)),
      // 例4(出力：(10, 30, 11, 30))
      Seq((10, 0, 12, 0), (11, 0, 11, 30), (10, 30, 11, 15)),
      // 例5(なし)
      Seq((9, 0, 17, 0), (19, 0, 21, 0)),
  )} println(solve(arg :_*) mkString ",")
}

36~39行目は、普段はこんな感じで書いていますｗ
case x1 :: x2 :: xs =>
x1 and x2 flatmap {i => i :: overlaps(Interval(i.end, x1.end max x2.end) :: xs)} getOrElse overlaps(x2 :: xs)