56. Merge Intervals

Topics: Array Sorting

Solution 1

• Time Complexity: O(nlogn), Space Complexity O(n)
• 先把 intervals 用 start 排序，排序後的 sortedIntervals 按照順序拿出，並放進去 mergedIntervals 。如果目前拿到的 interval 的 start ≤ mergedIntervals 的 end，代表這兩個 interval 有重疊要合併在一起，那就分別取 start 的 min 和 end 的 max。

Implementation

class Solution {
    fun merge(intervals: Array<IntArray>): Array<IntArray> {
        val sortedIntervals = intervals.sortedBy { it[0] }
        val mergedIntervals = mutableListOf<IntArray>()
        mergedIntervals.add(sortedIntervals.first())

        for (interval in sortedIntervals) {
            val lastInterval = mergedIntervals.last()
            if (interval[0] > lastInterval[1]) {
                mergedIntervals.add(interval)
            } else {
                val newLastInterval = intArrayOf(
                    min(interval[0], lastInterval[0]),
                    max(interval[1], lastInterval[1])
                )
                mergedIntervals.removeLast()
                mergedIntervals.add(newLastInterval)
            }
        }

        return mergedIntervals.toTypedArray()
    }
}

Solution 2

• Time Complexity: O(n), Space Complexity O(n)
• 先用一個迴圈預處理，把每一個 interval 存到 arr 中，arr[start] 會對到這個 interval 的 end ，如果遇到兩個 start 一樣的 interval 就留 end 比較大的。
• 下一個迴圈把 arr 掃過一遍，如果遇到 arr[i] 不是 -1，表示目前的 index 有一個 [i, arr[i]] 的 interval，這時候就把 interval 更新到 startIndex, endIndex 兩個暫存的 interval。如果下一個找到的 interval 的 start ≤ endIndex ，那表示他跟前一個 interval 重疊了，就把 endIndex 改成新的 arr[i]，否則這個 interval 沒有跟前一個重疊，目前的 startIndex, endIndex 就可以加到 mergedIntervals 裡面。

Implementation

class Solution {
    fun merge(intervals: Array<IntArray>): Array<IntArray> {
        val size = 10001
        val arr = IntArray(size){ -1 }
        var minIndex = intervals[0][0]

        for (interval in intervals) {
            val (start, end) = interval[0] to interval[1]
            arr[start] = max(arr[start], end)
            minIndex = min(minIndex, start)
        }

        val mergedIntervals = mutableListOf<IntArray>()
        var (startIndex, endIndex) = minIndex to arr[minIndex]

        for (i in 0 until size) {
            if (arr[i] == -1) continue
            if (i > endIndex) {
                mergedIntervals.add(intArrayOf(startIndex, endIndex))
                startIndex = i
            }
            endIndex = max(endIndex, arr[i])
        }

        mergedIntervals.add(intArrayOf(startIndex, endIndex))

        return mergedIntervals.toTypedArray()
    }
}