986.interval-list-intersections.md

986. Interval List Intersections

Two Pointers

We can apply the two pointers to the two list, and compare one by one to see if they are overlapped. If yes, try to find the interaction.

To find the intersection of two intervals, we can take the maximum of the two start points and the minimum of the two end points.

|-------|       a
    |------|    b
    |---|       intersection = max(a.start, b.start) to min(a.end, b.end)

Next is to move the pointer with smaller end, because the larger end might still overlap with upcoming intervals. It has higher chances to overlap with the subsequent intervals. If the two intervals have the same end, we can move either pointer, because neither one can overlap with the subsequent intervals. (Or we can move both pointers, because the intersection is the same.)

fun intervalIntersection(firstList: Array<IntArray>, secondList: Array<IntArray>): Array<IntArray> {
    val results = mutableListOf<IntArray>()
    var i = 0
    var j = 0
    while (i < firstList.size && j < secondList.size) {
        val first = firstList[i]
        val second = secondList[j]

        val notOverlapped = 
            first[1] < second[0] || 
            second[1] < first[0] 
        if (!notOverlapped) {
            results.add(intArrayOf(
                maxOf(first[0], second[0]),
                minOf(first[1], second[1])
            ))
        }
        // Move one pointer with smaller end, keep the larger end that 
        // has higher chances to overlap with the subsequent intervals.
        // This is applicable to the two intervals that are overlapped or not.
        if (first[1] < second[1]) {
            i++
        } else {
            j++
        }
    }
    return results.toTypedArray()
}

• Time Complexity: O(m + n) where m and n represent the size of two interval list.
• Space Complexity: O(m + n).