Leetcode 757. Set Intersection Size At Least Two

문제

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.

• inclusive interval 이 주어진다.
• 해당 개별 인터벌의 값을 최소 2개이상 포함하는 가장 작은 정수 배열의 길이를 구하라

예시

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

• [2, 3, 4, 8, 9]
• 해당 배열에 대해
  • [1, 3] 에 대해 2, 3 있고
  • [3, 7] 에 대해 3, 4 있고
  • [8, 9] 에 대해 8, 9 있음

제한

• $1 <= intervals.length <= 3000$
• $intervals[i].length == 2$
• $0 <= starti < endi <= 10^8$

풀이

1. interval을 끝나는 시간에 대해 오름차순, 시작하는 시간에 대해 내림차순으로 정렬한다.
2. 맨 처음 interval부터 최대한 끝에 있는 두 숫자를 선택한다. ( 선택시 정답으로 리턴할 값에 1씩 추가 )
3. 두번째 interval 선택시부터
   • 선택한 점들에 대해 점이 start보다 작을경우 새로 선택한다, 여기서 처음에 정렬한 것 때문에 두 점은 반드시 다음 interval의 end보다 작기 때문에 해당 부분은 생각하지 않는다.

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        ans = 0
        a = b = -1

        intervals.sort(key=lambda k: (k[1], -k[0]))

        for start, end in intervals:
            if a < start:
                ans += 2
                a = end
                b = end - 1
            elif b < start:
                ans += 1
                b, a = a, end

        return ans

• a가 b보다 항상 큰 상태를 유지하면서 해당 코드를 구현한 것