[LeetCode] 757. Set Intersection Size At Least Two

https://leetcode.com/problems/set-intersection-size-at-least-two/description/?envType=daily-question&envId=2025-11-20

LeetCode - Set Intersection Size At Least Two

문제 유형: 그리디, 투 포인터

문제 난이도: Hard

 

문제

You are given a 2D integer array intervals where intervals[i] = [starti, endi] represents all the integers from starti to endi inclusively.

A containing set is an array nums where each interval from intervals has at least two integers in nums.

• For example, if intervals = [[1,3], [3,7], [8,9]], then [1,2,4,7,8,9] and [2,3,4,8,9] are containing sets.

Return the minimum possible size of a containing set.

 

2D 정수배열 intervals[i] = [start_i, end_i]인 intervals가 주어진다.

start ~ end까지의 범위를 말한다.

 

Containing set은 각 interval 범위에서 적어도 두 개 이상씩 숫자가 있는 배열을 말한다.

Containing set의 최소 크기를 구하시오.

 

풀이

end에 대해서 오름차순, start에 대해서 내림차순을 하면, 오른쪽 끝이 정렬되어있으면서도 앞쪽이 더 큰 범위이다.

여기에서 각 interval에서 맨 뒤의 두 개의 숫자를 최대한 더하면서 가면 된다.

변수 a, b를 만들어서, 가장 최근에 추가된 두 숫자를 유지하고, a < b로 한다.

 

처음 interval을 고려해서, a=intervals[0][1]-1, b = intervals[0][1], 정답인 cnt = 2로 초기화한다.

이후, i=1부터 해서, i번째의 범위를 l, r이라고 한다.

- a >= l이면, a, b 모두 이번 interval에 있으므로 스킵한다

- a는 interval에 없고, b는 있다면, 1을 cnt에 추가해서, a = b, b = r로 업데이트하면 된다.

- a, b 모두 추가해야 할 수도 있다. 2를 cnt에 추가하며, a = r-1, b = r로 업데이트 하면 된다.

 

최종적으로 누적된 cnt를 반환하면 된다.

 

코드

C++

class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const auto &a, const auto &b){
            if(a[1] == b[1]) return a[0] > b[0];
            return a[1] < b[1];
        });

        int cnt = 2;
        int n = intervals.size();
        int b = intervals[0][1], a = b-1;
        for(int i = 1; i < n; i++) {
            const int l = intervals[i][0], r = intervals[i][1];
            if(a>=l) continue;
            const bool NO = l > b;
            cnt += 1+NO;
            a = NO?r-1:b;
            b = r;
        }

        return cnt;
    }
};