[LeetCode] 986. Interval List Intersections

https://leetcode.com/problems/interval-list-intersections/

Interval List Intersections - LeetCode

Interval List Intersections - Medium

 

인터벌벡터 A와 인터벌벡터 B가 주어진다. A와 B의 인터벌들 중 겹치는 구간을 출력하는 문제다.

 

각각의 인덱스를 i,j로 두자.

A[i]와  B[i]를 비교하여 

더 높은 시작점을 l 로, 더 낮은 끝점을 h로 두자.

만약 l<=h 라면, 겹치는 구간이 있는 것이고 l>h라면 겹치는 구간이 없는 것이다.

l<=h 일때 [l,h]를 추가해주자.

 

그 후, 끝점이 더 작은 벡터의 인덱스를 ++해주고, i,j가 둘다 A,B 크기보다 작을때까지 반복해주면 된다.

 

전체 풀이 코드

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        vector<vector<int>> ret;
        int i=0,j=0,l,h;
        while (i<firstList.size() && j<secondList.size()) {
            l = max(firstList[i][0], secondList[j][0]);
            h = min(firstList[i][1], secondList[j][1]);
            if (l<=h) ret.push_back({l,h});
            if (firstList[i][1] < secondList[j][1]) i++;
            else j++;
        }
        return ret;
    }
};