Soyo

May Leetcode Challenge - Day 23

Interval List Intersections

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Note:

  • 0 <= A.length < 1000
  • 0 <= B.length < 1000
  • 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution

Because two arrays are sorted, we can do a straight check.
Compare one in A by one in B, move to next element when current element's head is lower.

class Solution {
    func intervalIntersection(_ A: [[Int]], _ B: [[Int]]) -> [[Int]] {
        var moving: Int = 0
        
        var indexA = 0
        var indexB = 0
        
        var res = [[Int]]()

        while (indexA < A.count) && (indexB < B.count) {
            let valA = A[indexA]
            let valB = B[indexB]
            
            if let intersection = valA.intersectionWith(valB) {
                res.append(intersection)
            }
            
            if valA[1] > valB[1] {
                indexB += 1
            }else{
                indexA += 1
            }
        }

        return res
    }
}

extension Array where Element == Int {
    func intersectionWith(_ range: [Int]) -> [Int]?{
        if self[1] < range[0] || self[0] > range[1] {
            return nil
        }
        return [self[0] >= range[0] ? self[0] : range[0], self[1] <= range[1] ? self[1] : range[1]]
    }
}

Comments