#LeetCode:986. Interval List Intersections

灆洢 2020-05-23 17:29:15

此題要找出兩邊區間群的交集區間群。

由於有兩條區間群都有排序過,所以就是兩邊開始從頭比較區間,如果兩邊所選出的區間有交集就產生出一個交集區間,接著將比較前面區間的那條區間群再往後一個去做一樣的判斷,直到兩邊區間群都沒區間為止。

Kotlin(284ms)

/*******************************************************
 * LeetCode 986. Interval List Intersections           *
 * Author: Maplewing [at] knightzone.studio            *
 * Version: 2020/05/23                                 *
 *******************************************************/
class Solution {
    fun intervalIntersection(A: Array<IntArray>, B: Array<IntArray>): Array<IntArray>     {
        if (A.size == 0 || B.size == 0) return Array<IntArray>(0, { IntArray(0) })

        val result = mutableListOf<IntArray>()
        var aIndex = 0
        var bIndex = 0
        while (aIndex < A.size && bIndex < B.size) {
            if (A[aIndex][0] in B[bIndex][0]..B[bIndex][1] ||
                B[bIndex][0] in A[aIndex][0]..A[aIndex][1]
            ) {
                result.add(intArrayOf(
                    Math.max(A[aIndex][0], B[bIndex][0]),
                    Math.min(A[aIndex][1], B[bIndex][1])
                ))
            } 

            if (A[aIndex][1] < B[bIndex][1]) {
                ++aIndex
            } else if (A[aIndex][1] == B[bIndex][1]) {
                ++aIndex
                ++bIndex
            } else {
                ++bIndex
            }
        }

        return result.toTypedArray()
    }
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料