Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example, Given

[1,3],[2,6],[8,10],[15,18]

return

[1,6],[8,10],[15,18]

case class Interval(start: Int, end: Int)

def merge(intervals: List[Interval]):List[Interval] = {
  var merged: List[Interval] = Nil
  for (interval <- intervals.sortBy(_.start)) {
    if (merged.isEmpty || merged.head.end < interval.start) merged = interval :: merged
    else {
      val start = merged.head.start min interval.start
      val end = merged.head.end max interval.end
      merged = new Interval(start, end) :: merged.tail
    }
  }
  merged.reverse
}

def wrap(lst: List[(Int,Int)]):List[Interval] = lst map {
  case (i,j) => new Interval(i,j)
}

val test1 = wrap(List((1,3),(2,6),(8,10),(15,18)))
merge(test1)