1 of 2

Here's a relatively straightforward solution in Scala. It shouldn't be too difficult to port to another language.

case class Range(name: String, left: Double, right: Double)

def apply(ranges: Vector[Range], newRange: Range) = {
  // Find ranges to the left of the new range that do not overlap
  val (left, overlapAndRight) = 
    ranges.span(_.right <= newRange.left)

  // Find ranges to the right of the new range that do not overlap
  val (overlap, right) =
    overlapAndRight.span(_.left < newRange.right)

  // Get the leftmost overlapping item, if any
  val leftSplit = overlap.headOption
    // Make sure it hangs past the new range's left edge
    .filter(_.left < newRange.left)
    // Create a new range that doesn't overlap
    .map((x) => Range(x.name, x.left, newRange.left))

  // Get the rightmost overlapping item, if any
  val rightSplit = overlap.lastOption
    // Make sure it hangs past the new range's right edge
    .filter(_.right > newRange.right)
    // Create a new range that doesn't overlap
    .map((x) => Range(x.name, newRange.right, x.right))

  // Return a new sorted list of ranges
  (left ++ leftSplit :+ newRange) ++ rightSplit ++ right
}

val ranges = Vector[Range](
  Range("red",   12.5, 13.8),
  Range("blue",   0.0,  5.4),
  Range("green",  2.0, 12.0),
  Range("yellow", 3.5,  6.7),
  Range("orange", 6.7, 10.0))

val flattened = ranges.foldLeft(Vector.empty[Range])(apply)
flattened foreach println