1. 문제 소개

Constraints:

• 1 <= intervals.length <= 3000
• intervals[i].length == 2
• 0 <= start_i < end_i <= 10^8

757. Set Intersection Size At Least Two

2. 나의 풀이

처음에는 문제를 잘 이해하지 못했다. 다음과 같은 비유를 들어 설명했을 때 이해했다.

"구간 하나를 '두 명 이상 배치해야 하는 회의실 예약 시간대'라고 생각해 보자. 타임라인(시간축)이 있고, 각 구간 [L, R]은 “이 시간 동안 최소 2명이 있어야 한다”는 요구사항이다."

이렇게 말하니 이해가 됐다. 하지만 문제를 푸는 것은 쉽지가 않았다.
힌트를 보고 이전 숫자 2개를 추적해 풀 수 있었다.
시간복잡도는 정렬에 필요한 $O(n \,log n)$이다.

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[1], -x[0]))
        # intervals를 (끝점 오름차순, 시작점 내림차순)으로 정렬
        # - 끝점이 작은 구간부터 처리하면, 오른쪽 끝에 찍는 점들이
        #   이후의 구간에도 재사용될 가능성이 커진다.
        # - 같은 끝점을 가진 구간들에서는 시작점을 큰 것부터 처리함으로써
        #   더 긴 구간이 나중에 오도록 한다(그리디 전략에 유리).

        ans = 0
        prev1, prev2 = 10 ** 8  + 1,  10 ** 8  + 1
        # 지금까지 선택한 점들 중 "가장 큰 두 점"을 prev1, prev2로 관리
        # - 초기값은 모든 가능한 구간 범위 밖(10^8+1)으로 설정하여
        #   어떤 구간에도 포함되지 않도록 함.
        # - 관례상 prev1: 가장 큰 점, prev2: 두 번째로 큰 점을 의미하도록 유지.

        for s, e in intervals:
            # 각 구간 [s, e]에 대해,
            # 이미 선택한 점(prev1, prev2) 중 몇 개가 이 구간 안에 들어있는지 센다.
            cnt = 0
            if s <= prev1 <= e:
                cnt += 1  # prev1이 현재 구간 [s, e] 안에 포함되면 카운트 증가
            if s <= prev2 <= e:
                cnt += 1  # prev2도 포함되면 추가로 카운트 증가

            if cnt == 2:
                # 이미 이 구간 안에 선택된 점이 2개 이상 있으므로
                # 새로운 점을 추가할 필요가 없음.
                continue
            elif cnt == 1:
                # 이 구간 안에는 현재까지 선택된 점이 1개만 있으므로,
                # 하나만 더 추가하면 된다.
                # 그리디 전략상, "가장 오른쪽 끝 e"에 점을 추가하는 것이
                # 이후 구간들에도 재사용될 가능성이 높다.
                prev1, prev2 = e, prev1
                # e를 가장 큰 점(prev1)으로 두고,
                # 기존의 prev1를 prev2로 내려 배치.
                # (현재 코드에서는 어떤 점이 실제로 구간 안에 있었는지는
                #  별도로 구분하지 않고 단순히 prev1/prev2를 재배치하는 방식으로 처리.)
                ans += 1
            elif cnt == 0:
                # 이 구간 안에 선택된 점이 하나도 없으므로,
                # 이 구간을 만족시키기 위해 최소 2개의 점을 새로 추가해야 한다.
                # 그리디 전략상, 가장 오른쪽 두 점인 (e-1, e)를 선택하는 것이
                # 뒤에 나올 구간들에서 재사용성을 극대화하는 선택이다.
                prev1, prev2 = e, e - 1
                # 가장 큰 점(prev1) = e, 두 번째 점(prev2) = e-1로 설정한다.
                ans += 2
        return ans
        # ans에는 지금까지 추가한 점 개수(집합 S의 크기)가 누적되어 있으며,
        # 모든 구간이 |S ∩ interval| ≥ 2 를 만족하도록 만든 최소 크기이다.

3. 다른 풀이

풀이의 접근법은 같다.
이것도 시간복잡도는 $O(n \, log n)$이다.

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        n = len(intervals)

        intervals.sort(key=lambda x: x[1])
        # 구간을 끝점(end) 기준 오름차순으로 정렬.
        # 끝점이 작은 구간부터 처리하면,
        # 나중에 등장하는 구간들과의 겹침이 극대화되어
        # 이미 선택한 점(prev1, prev2)을 재사용하기 유리하다.

        prev1 = intervals[0][1] - 1
        prev2 = intervals[0][1]
        # 첫 구간의 끝점을 기준으로 두 점(prev1, prev2)을 선택한다.
        # - prev2: 구간의 끝점 e
        # - prev1: e-1
        # 두 점은 항상 "현재까지 선택한 점 중 가장 큰 두 점"이 되도록 유지한다.
        # 첫 구간은 무조건 두 점을 필요로 하므로 c = 2 로 시작.

        c = 2  # 지금까지 선택된 점의 개수

        for i in range(1, n):
            s, e = intervals[i]
            # 각 구간을 하나씩 확인하면서,
            # prev1, prev2 중 몇 개가 이 구간 [s, e]를 커버하는지 판단한다.

            if prev2 < s:
                # prev1, prev2 둘 다 현재 구간 왼쪽에 있고,
                # 즉 "이 구간과 겹치지 않음" → 포함된 점 개수 cnt = 0
                # 이 구간을 만족시키려면 새 점 2개 필요.
                prev1 = e - 1
                prev2 = e
                c += 2

            elif prev1 < s:
                # prev1은 구간 밖이지만 prev2는 구간 안에 있음 → cnt = 1
                # 1개 부족하므로 하나만 새로 추가해야 한다.

                if e == prev2:
                    # prev2가 이미 e라면,
                    # 새로 넣는 점(prev1)은 (e - 1)이어야 오른쪽에서 최대 재사용.
                    prev1 = e - 1
                else:
                    # prev2가 e가 아니라면,
                    # 현재 구간의 끝 e를 새 점으로 추가하는 것이 최적.
                    prev1 = e

                # prev1, prev2가 "정렬된 두 큰 점" 형태가 되도록 재정렬
                prev1, prev2 = min(prev1, prev2), max(prev1, prev2)

                c += 1

            # prev1 >= s 이면 → prev1, prev2 둘 다 구간 안 → cnt = 2
            # 이 경우는 아무 점도 추가할 필요 없음.

        return c

4. 결론

비슷한 문제를 푼 경험이 있어서 쉽게 풀 수 있을 줄 알았는데 아니었다.
역시 꾸준한 문제풀이가 중요하다.