object InsertIntervalProgram {
def insertInterval(intervals: List[(Int, Int)], newInterval: (Int, Int)): List[(Int, Int)] = {
var result = List.empty[(Int, Int)]
var i = 0
val n = intervals.length
var current = newInterval
// 1. Add all intervals that end BEFORE the new interval starts.
// These cannot overlap.
while (i < n && intervals(i)._2 < current._1) {
result = result :+ intervals(i)
i += 1
}
// 2. Merge all intervals that DO overlap with the new interval.
// Overlap condition: intervals(i).start <= newInterval.end
while (i < n && intervals(i)._1 <= current._2) {
current = (
math.min(current._1, intervals(i)._1),
math.max(current._2, intervals(i)._2)
)
i += 1
}
// Add the merged interval
result = result :+ current
// 3. Add all remaining intervals (those starting AFTER new interval ends)
while (i < n) {
result = result :+ intervals(i)
i += 1
}
result
}
def main(args: Array[String]): Unit = {
val intervals = List((1, 3), (6, 8), (13, 18))
val newInterval1 = (9, 11)
val updated1 = insertInterval(intervals, newInterval1)
val newInterval2 = (2, 5)
val updated2 = insertInterval(updated1, newInterval2)
println("Updated intervals:")
updated2.foreach { case (s, e) => print(s"[$s,$e] ") }
}
}
/*
run:
Updated intervals:
[1,5] [6,8] [9,11] [13,18]
*/
