[leetcode 986] 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]]

 

Note:

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

풀이

- 투포인터 사용

- A와 B 배열 각각을 가리키는 포인터를 사용한다. i와 j

- A와 B가 겹친다면 그 범위는: start = A[i][0]과 B[j][0]의 최댓값,  end= A[i][1]과 B[j][1]의 최솟값 -> [start,end]일 것이다.

- A와 B가 겹치지 않는다면  start>end일 것이다. 따라서 start<=end일때만 답이 된다.

- i와 j를 움직이는 조건: A[i]와 B[j]의 오른쪽 끝값을 비교하여 작은 배열의 인덱스를 움직인다.

 

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        
        vector<vector<int>> answer;
        
        int i=0, j=0;
        
        while(i<A.size() && j<B.size()){
            
            int start = max(A[i][0], B[j][0]);
            int end = min(A[i][1], B[j][1]);
            
            if(start<=end){
                answer.push_back({start, end});
            }
                
            if(A[i][1]<B[j][1]){
                i++;
            }else {
                j++;
            }
        }
        
        return answer;
        
        
    }
};