Inserting an interval in a sorted list of disjoint intervals

Question

I have a sorted list of disjoint intervals and an interval, e.g. [(1, 5), (10, 15), (20, 25)] and (12, 27). So, (12,27) is the interval I want to merge them into a sorted list of disjoint intervals: [(1, 5), (10, 27)].

Answer 1

Here is my non-idiomatic scala solution full of vars. The solution looks longer than it should be because I have poor implementations of append and insert on lists which only support the prepend operation.

The algo is as follows:

1. Scan to divide the list of intervals into two lists ones that don't overlap with the new interval and ones that do. Non-overlapping intervals are ones that begin either entirely after or entirely before the new interval. Also if we were to insert a new interval it would be after the highest interval that is lower than it. At this stage we have a list of overlapping intervals and a list of non-overlapping ones.
2. If there are no overlaps then the new interval either earlier than all given intervals or after all intervals or in between two intervals (still no overlap).
3. If there is an overlap merge the overlapping intervals with the new interval. The overlapping interval's start is min(new interval's start, smallest overlapping interval's start). We can calculate the end similarly. Now insert the overlapping interval in the position calculated earlier.

Here is the code:

object trial {
  val intervals1 = List((1, 2), (4, 6), (7, 8), (16, 17)))
  val intervals2 = List((1, 5), (10, 15), (20, 25)

  val newInterval1 = (11, 12)
  val newInterval2 = (12, 27)

  // Interval algo test.
  val result1 = Merge(intervals1, newInterval1)   // result1  : List((1,2), (4,6), (7,8), (11,12), (16,17))
  val result2 = Merge(intervals2, newInterval2)   // result2  : List[(Int, Int)] = List((1,5), (10,27))
  }

object Merge{
  def append[T](list: List[T], el: T): List[T] = {
    (el :: list.reverse).reverse
  }
  def insert[T](list: List[T], pos: Int, elem: T): List[T] = {
    var newList = List.empty[T]
    val reversePos = list.length - pos
    list.reverse.zipWithIndex foreach {
      case(el, i) if i == reversePos => {
        newList = elem :: newList
        newList = el :: newList
      }
      case (el, i) => newList = el :: newList
    }
    newList
  }

  def apply(list: List[(Int, Int)], interval: (Int, Int)): List[(Int, Int)] = {
    val (min, max) = interval
    var newList = List.empty[(Int, Int)]
    // Store potentially overlapping stuff.
    var overlap = List.empty[(Int, Int)]
    // Maintain the position to begin merge.
    var posInsert = 0
    list.zipWithIndex foreach { case(intervalz, i) =>
      if (intervalz._2 < min) {
      // Does not overlap but an insert will be after the highest of these.
        posInsert = i
        newList = append(newList, intervalz)
      } else if (intervalz._1 > max) {
        // Does not overlap.
        newList = append(newList, intervalz)
      } else overlap = append(overlap, intervalz)
    }
    if (overlap isEmpty) {
      if (posInsert == 0) newList = interval :: newList
      else newList = insert(newList, posInsert + 1, interval)
    } else {
      // Start of new interval is the lower of the first overlap's start or the interval's start.
      val startOfInterval = Math.min(overlap.head._1, min)
      // Enf of interval is higher of last overlap's end or interval's end.
      val endOfInterval = Math.max(overlap.head._2, max)
      // Insert the merged interval after the highest interval smaller than the start of the new internval.
      if (posInsert == 0) newList = (startOfInterval, endOfInterval) :: newList
      else newList = insert(newList, posInsert + 1, (startOfInterval, endOfInterval))
    }
    newList
  }
}

It passes the tests mentioned here and is O(N).

EDIT. The algo version of it:

intervals = [....]
newInterval = (12, 27)
newList = []
overlappingList = []
posInsert = 0
i = 0

while (i < intervals.size)
  if (intervals[i].max < newInterval.min)
    posInsert = i
    append(newList, intervals[i]) 
  else if (intervals[i].min > newInterval.max)
    append(newList, intervals[i])
  else
    append(overlappingList, intervals[i])
  i++

if (overlap isEmpty)
  if (posInsert == 0) prepend(newList, newInterval)
  else insert(newList, posInsert + 1, newInterval)
else
  start = Min(overlappingList[i].min, newInterval.min)
  end = Max(overlappingList[i].max, newInterval.max)
  if (posInsert == 0) prepend(newList, newInterval)
  else insert(newList, posInsert + 1, new Interval(start, end))
return newList

Answer 2

You can model your problem with graph, in fact your intervals are nodes and they are connected to each other if they have common parts (e.g (12,27) is connected to (15,20)) now first you should find connected components, then in each connected component find min value of start (e.g 10) and max value of end (e.g 25). It's good to see Interval Graphs.

Answer 3

pseudo:

list = ...
u = (12,27)
i = 0
newlist = []

while (max(list[i]) < min(u))  //add all intervals before intersection
  newlist.add(list[i++])
mini = i

while (min(list[i]) < max(u))  // skip all intersecting intervals
  i++
maxi = i

newlist.add((min(list[mini],u),max(list[maxi],u)) // add the new interval

while (i < list.length) // add remaining intervals
  newlist.add(list[i++])

return newlist