- No, it's clear from problem description.
Input:
Output:
- The intervals is empty.
- The new interval is not overlapped with any intervals. (before all intervals, after all intervals, between all intervals)
fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
val results = mutableListOf<IntArray>()
var i = 0
// Add all non-overlapping interval before the new interval
// interval[i] newInterval
// |---------| |_________|
while (i < intervals.size && intervals[i][1] < newInterval[0]) {
results.add(intervals[i])
i++
}
// intervals[i] is partially overlapped with new interval
// |----------|
// |_________|
// Or
// |-------|
// |______|
var merged = newInterval
while (i < intervals.size && isOverlapped(intervals[i], merged)) {
// Or equivalent to
// while (i < intervals.size && intervals[i][0] <= merged[1]) {
merged[0] = minOf(intervals[i][0], merged[0])
merged[1] = maxOf(intervals[i][1], merged[1])
i++
}
results.add(merged)
// add the remaining non-overlapping intervals
while (i < intervals.size) {
results.add(intervals[i])
i++
}
return results.toTypedArray()
}
Or equivalently, we can use for loop to iterate through the intervals. (but more complex, not recommended)
fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
val results = mutableListOf<IntArray>()
var merged = newInterval
// Check if the newInterval is added.
var isAdded = false
for (i in 0 until intervals.size) {
if (isOverlapped(intervals[i], merged)) {
if (!isAdded) {
results.add(merged)
isAdded = true
}
merged[0] = minOf(merged[0], intervals[i][0])
merged[1] = maxOf(merged[1], intervals[i][1])
} else {
// The newInterval is ahead of all intervals, we have to add it first.
if (!isAdded) {
if (merged[1] < intervals[i][0]) {
results.add(merged)
isAdded = true
}
}
results.add(intervals[i])
}
}
// The newInterval is the last interval and not overlapped with any intervals.
if (!isAdded) results.add(merged)
return results.toTypedArray()
}
- Time Complexity:
O(n)
. - Space Complexity:
O(1)
.