Question

How to detect whether any intervals overlap in a list of start and end times with Scala

Answer 1

object Main {

  def hasOverlap(intervals: List[(Int, Int)]): Boolean = {
    if intervals.isEmpty then
      true
    else
      // Sorting is essential because once intervals are ordered by 
      // start time, any overlap can only occur between adjacent intervals.
      val sorted = intervals.sortBy(_._1)
      // (5,9), (11,12), (15,17)

      // (5,9) and (11,12) → 11 < 9? No
      // (11,12) and (15,17) → 15 < 12? No

      // The loop compares each interval with the one before it.
      val overlapFound =
        sorted
          .sliding(2)
          .exists { pair =>
            val (prev, curr) = (pair(0), pair(1))
            curr._1 < prev._2 // Overlap found
          }

      !overlapFound // No overlap
  }

  def main(args: Array[String]): Unit = {
    val intervals = List(
      (11, 12),
      (5, 9),
      (15, 17)
    )

    if hasOverlap(intervals) then
      println("There are NO overlapping intervals")
    else
      println("There ARE overlapping intervals")
  }
}



/*
run:

There are NO overlapping intervals

*/

 

70+ SQL courses for beginners and professionals