[Leetcode] 757. Set Intersection Size At Least Two

[start, end] 로 주어지는 간격(interval)들의 배열이 주어진다. 이후 모든 간격의 원소가 두개씩 포함하는 배열의 가장 작은 크기를 구해야 하는 문제. [[1, 2], [2, 3]] 처럼 연속된 점이 있다면 [1, 2, 3] 처럼 죽 그어버리면 되지만 [[1, 2], [8, 9]] 처럼 간격들이 떨어져 있는 경우 가장 작은 크기를 얻기 위해서는 중간에 빈 부분을 빼야한다([1, 2, 8, 9] 의 크기는 4).

먼저 간격들을 정렬해야 하는데 다행히 intervals의 길이 최댓값이 3000 이라 편하게 .sort() 를 했다.end 가 작은 순서부터, 그리고 end가 같다면 start 가 큰 순서부터 오도록 정렬했다. 어차피 end, end -1 두 개만 배열에 들어가면 되기 때문에 end 가 같다면 start 는 얼마나 길던지 상관없다.

이후 첫번째로 큰 값 s1, 두번째로 큰 값 s2 를 정한 뒤 각 간격과의 관계를 정하면 된다. 이 때 s1은 b 보다 커질 수 없으므로 a와의 관계만 보면 된다(매 반복마다 s1에 할당되는 값은 b 뿐이므로).

a 가 s1 보다도 크다면 이전 간격보다 훨씬 뒤쪽에 위치한 새로운 간격이므로 s1 와 s2 모두 갱신하고 size 에 2를 추가한다.
a 가 s2 보다는 크고 s1 보다 작다면 기존 간격과 한 칸이 겹친다는 뜻으로 size 에 1을 추가하고 s2는 s1으로, s1은b로 갱신한다.
a가 s2 보다도 작다면 정렬되어 있는 이전값의 b-1 보다도 작다는 뜻이므로 별다른 작업이 필요없다.

function intersectionSizeTwo(intervals: number[][]): number {
    intervals.sort((a, b) => {
        if (a[1] === b[1]) {
            return b[0] - a[0]
        }

        return a[1] - b[1]
    })

    let s1 = -1 // b 보다 작거나 같음
    let s2 = -2
    let size = 0

    for (const [a, b] of intervals) {
        if (s2 < a) {
            if (s1 < a) {
                s1 = b
                s2 = b -1
                size += 2
            } else {
                s2 = s1
                s1 = b
                size += 1
            }
        }
    }

    return size;
};