[Codility] MaxNonoverlappingSegments, 코딜리티 그리디 greedy

문제는 다음과 같다.

풀이 방법으로 생각했던 것은 다음과 같다.
모든 세그먼트를 하나의 평면으로 통합시키면, 중복은 전부 연결이 된다.
이 때 떨어져있는 세그먼트들의 수를 세면 된다.

통과되는 답은 다음과 같다.

계속 50프로만 되다가 다른 블로그를 보고 참고했는데..

public class MaxNonoverlappingSegments {

    public static void main(String args[]) {
        int count = solution(new int[] {1, 3, 7, 9, 9, 10}, new int[] {5, 6, 8, 9, 10, 10});

        System.out.println(count);
    }

    public static int solution(int[] A, int[] B) {
        if (A.length < 1) {
            return 0;
        }

        if (A.length < 2) {
            return 1;
        }

        int end = B[0];
        int count = 1;
        for (int i = 1; i < A.length; ++i) {
            if (end < A[i]) {
                ++count;
                end = B[i];    // **Here 1.**
            }
            // end = B[i];    // **Here 2.**
        }

        return count;
    }

}

위 코드에서 1번은 통과가 되고 2번 위치에 두면 50프로만 통과 된다.
이게 2번이라고 생각했던 이유로는, 중복된 세그먼트라면 이제 끝나는 지점을 갱신해야 한다고 생각했다.

그래서 아래와 같이 아니 이거 내가 이런 테스트케이스도 해봤는데 제대로 된게 맞는가? 하고 문의도 했다.

아니 근데 이런, 글을 쓰다가 깨달았다.

이거 그리디하게 하는거라서, 꼭 중첩된걸 갱신하지 않더라도 그냥 최대 개수를 구하면 된다.
즉, 중첩된 것은 그냥 무시하고 그 다음 중첩되지 않는 가장 가까운 것을 찾아서 해당 끝단으로 갱신하면 답이 나온다.

그래서 1번 위치에 있어서 카운트를 세주는 경우에 (즉, 중첩을 벗어나는 경우에) 끝단을 업데이트 하는 것 이었다.

..아 괜히 문의 넣었네 ^.^;;