57. 插入区间 - Kotlin 合并区间 模拟

Problem: 57. 插入区间

思路

由于题干指明了原区间序列是有序且无重叠的，可以为我们省去许多功夫

我们用一个min和一个max记录当前合并区间的左边界和右边界，且初始化为newInterval的左边界和右边界

顺序遍历intervals，可以对遍历到的interval分为两种情况：

• 当interval和当前的合并区间无重叠部分时，可以直接将interval添加至结果res中
• 当interval和当前的合并区间有重叠部分时，即interval可以和当前的合并区间再次合并，新的合并区间中左边界min应当取interval[0]和min中较小的一个，右边界max应当取interval[1]和max中较大的一个

由于intervals本身是有序的，当interval不再满足该条件时，即可将合并区间[min,max]插入res中

复杂度

• 时间复杂度:

• 空间复杂度: ，主要是存储返回结果用的ArrayList，如果不考虑这个也可以认为是

Code

class Solution 
fun Solution.insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
    if (intervals.size == 0) return arrayOf(newInterval)

    val res = ArrayList<IntArray>()
    var min = newInterval[0]
    var max = newInterval[1]
    var flag = false
    var done = false

    for (interval in intervals) {
        if ((interval[0] <= min && interval[1] >= min)
            || (interval[0] <= max && interval[1] >= max)
            || (interval[0] >= min && interval[1] <= max)
        ) {
            min = Math.min(min, interval[0])
            max = Math.max(max, interval[1])
            flag = true
        } else if (flag) {
            res.add(intArrayOf(min, max))
            res.add(interval)
            flag = false
            done = true
        } else {
            res.add(interval)
        }
    }
    if (!done) {
        res.add(intArrayOf(min, max))
    }

    return res.sortedBy { it[0] }.toTypedArray()
}