import Foundation
func insertInterval(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
var result: [[Int]] = []
var i = 0
let n = intervals.count
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.append(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][0] <= current[1] {
current[0] = min(current[0], intervals[i][0])
current[1] = max(current[1], intervals[i][1])
i += 1
}
// Add the merged interval
result.append(current)
// 3. Add all remaining intervals (those starting AFTER new interval ends)
while i < n {
result.append(intervals[i])
i += 1
}
return result
}
// Usage:
let intervals = [
[1, 3],
[6, 8],
[13, 18]
]
let newInterval1 = [9, 11]
var updated = insertInterval(intervals, newInterval1)
let newInterval2 = [2, 5]
updated = insertInterval(updated, newInterval2)
print("Updated intervals:")
for iv in updated {
print("[\(iv[0]),\(iv[1])]", terminator: " ")
}
/*
run:
Updated intervals:
[1,5] [6,8] [9,11] [13,18]
*/
