Finding all the intervals that contain a given interval.Two implementations are given and tested.1) Using TreeSets and ranges (from, and until).2) Using HashSets and groupBy on all the values of all the intervals.

ContainsIntervalsTest.scala

package com.liveperson.predictivedialer.examples.misc

import scala.util.Random
import scala.collection.immutable.{HashSet, SortedSet, TreeSet}
import org.junit.runner.RunWith
import org.scalatest.junit.JUnitRunner
import org.scalatest.{Matchers, FlatSpec}

/**
 * Created with IntelliJ IDEA.
 * User: mishaelr
 * Date: 1/28/14
 * Time: 1:30 PM
 */
@RunWith(classOf[JUnitRunner])
class ContainsIntervalsTest extends FlatSpec with Matchers{

  val rand = new Random(17)
  val supremum = 1000
  val maximalLength = 8
  val numOfIntervals = 1000
  val numOfTrials = 1000

  def generateInterval = {
    val i = rand.nextInt(supremum)
    (i, i + rand.nextInt(maximalLength))
  }

  val intervalsSet = Set[(Int, Int)]() ++ Iterator.fill(numOfIntervals)(generateInterval)
  println("Intervals are:\n" + intervalsSet.mkString(", "))
  val treeContainsInterval = new TreeContainsInterval(TreeSet[(Int, Int)]() ++ intervalsSet)
  val hashContainsInterval = new HashContainsInterval(HashSet[(Int, Int)]() ++ intervalsSet)

  "Tree results" should "equal hash results" in {

    for (i <- 1 to numOfTrials) {
      val interval = generateInterval
      val treeResult = treeContainsInterval(interval)
      val hashResult = hashContainsInterval(interval)
      println(
        """-------------------------------
          |Trial number: %s
          |Interval is: %s
          |Results using trees are:
          | %s
          |Results using hash are:
          | %s""".format(i, interval, treeResult.mkString(", "), hashResult.mkString(", ")).stripMargin)

      implicit class RichPair(interval: (Int, Int)) {
        def contains(other: (Int, Int)) = interval._1 <= other._1 && interval._2 >= other._2
      }

      assert(treeResult === hashResult)
      assert(hashResult forall(_.contains(interval)))
      assert(!(intervalsSet -- hashResult).exists(_.contains(interval)))
    }
  }
}


trait ContainsInterval[T <: Set[(Int, Int)]] {
  def intervalsSet: T
  def apply(interval: (Int, Int)): T
}


class TreeContainsInterval(val intervalsSet: TreeSet[(Int, Int)]) extends ContainsInterval[SortedSet[(Int, Int)]]{
  val endsSet = intervalsSet.map(_.swap)

  def apply(interval: (Int, Int)) = {
    endsSet.from((interval._2, Int.MinValue)).map(_.swap) intersect intervalsSet.until((interval._1, Int.MaxValue))
  }
}


class HashContainsInterval(val intervalsSet: HashSet[(Int, Int)]) extends ContainsInterval[HashSet[(Int, Int)]] {
  val mapping = for {
    (i, j) <- intervalsSet
    k <- i to j
  } yield (k, (i, j))

  def apply(interval: (Int, Int)) = {
    val grouped = mapping.groupBy(_._1)
    val resultOption = for {
      containStart <- grouped.get(interval._1)
      containEnd <- grouped.get(interval._2)
    } yield containStart.map(_._2) intersect containEnd.map(_._2)

    resultOption match {
      case Some(set) => set
      case _ => HashSet[(Int, Int)]()
    }
  }
}