fun insertInterval(intervals: MutableList<IntArray>, newInterval: IntArray): MutableList<IntArray> {
val result = mutableListOf<IntArray>()
var i = 0
val n = intervals.size
var current = newInterval
// 1. Add all intervals that end BEFORE the new interval starts.
// These cannot overlap.
while (i < n && intervals[i][1] < current[0]) {
result.add(intervals[i])
i++
}
// 2. Merge all intervals that DO overlap with the new interval.
// Overlap condition: intervals[i].start <= newInterval.end
while (i < n && intervals[i][0] <= current[1]) {
current = intArrayOf(
minOf(current[0], intervals[i][0]),
maxOf(current[1], intervals[i][1])
)
i++
}
// Add the merged interval
result.add(current)
// 3. Add all remaining intervals (those starting AFTER new interval ends)
while (i < n) {
result.add(intervals[i])
i++
}
return result
}
fun main() {
val intervals = mutableListOf(
intArrayOf(1, 3),
intArrayOf(6, 8),
intArrayOf(13, 18)
)
val newInterval1 = intArrayOf(9, 11)
var updated = insertInterval(intervals, newInterval1)
val newInterval2 = intArrayOf(2, 5)
updated = insertInterval(updated, newInterval2)
print("Updated intervals:\n")
for (iv in updated) {
print("[${iv[0]},${iv[1]}] ")
}
}
/*
run:
Updated intervals:
[1,5] [6,8] [9,11] [13,18]
*/
