[Leetcode] 986. Interval List Intersections 문제풀이

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

Interval List Intersections - LeetCode

 

문제 내용

2개의 스케줄 리스트가 있는데 겹치는 부분 출력하기

 

Example 1:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]

Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

 

문제 풀이

한칸씩 서로 비교하면 된다.

한칸씩 이동할 때는 경우의 수가 3가지 있다.

 

1. 겹치지 않고 A가 뒤에 있는 경우

A

    B

2. 겹치지 않고 B가 뒤에 있는 경우

    A

B

3. 겹치는 경우

 

1번 경우에는 A를 한칸 이동

2번 경우에는 B를 한칸 이동

3번 경우에는 end point가 작은쪽이 이동

 

겹치는 구간은 start가 max인 값과 end가 min값으로 구할 수 있다.

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