전부 겹치는 선분 2

1차원 상에서 여러 선분이 전부 겹치는지 판단하는 방법
x1, x2가 있고 x1 < x2라고 할 때, min(x2) >= max(x1)이면 모든 선분이 겹친다고 할 수 있다.

문제

1차원 직선 상에 N개의 선분이 놓여있다.
그 중 한 개를 제거했을 때, N-1 개의 선분이 전부 겹치도록 만들 수 있는지 판단하라.

코드 1

		for (int i = 0; i < n; i++) {
			boolean allOver = true;
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					if (i == j || i == k || j == k)
						continue;

					if (x2[j] < x1[k] || x1[j] > x2[k]) {
						allOver = false;
						break;
					}
				}
			}

			if (allOver) {
				System.out.println("Yes");
				return;
			}
		}

		System.out.println("No");

• 제거 된 선분을 제외한 모든 선분을 직접 비교하면서 겹치는지 판단
• 겹침 판단 알고리즘 시간복잡도 : $O(n^2)$

코드 2

        for(int skip = 0; skip < n; skip++) {
            int maxX1 = 0;
            int minX2 = INT_MAX;
            boolean possible = false;
            for(int i = 0; i < n; i++) {
                if(i == skip) continue;

                // 시작점 중 가장 뒤에 있는 좌표와 끝점 중 가장 앞에 있는 점의 좌표를 확인합니다.
                maxX1 = Math.max(maxX1, x1[i]);
                minX2 = Math.min(minX2, x2[i]);
            }

            // 만약 어느 한 선분이라도 시작점이 다른 선분의 끝점보다 뒤에 온다면
            // 선분이 전부 겹칠 수 없습니다.
            if(minX2 >= maxX1)
                possible = true;
            else
                possible = false;
            
            // 만약 한 가지 방법이라도 전부 겹치는 지점을 만들 수 있다면,
            // 하나의 선분을 적절하게 제거했을 때 전부 겹칠수 있다는 것이 되므로 할 수 있게 됩니다.
            if(possible)
                ans = true;
        }

        if(ans)
            System.out.print("Yes");
        else
            System.out.print("No");

• $x1 < x2$ 의 성질을 이용하여 $O(n)$만에 모든 선분이 겹치는지 판단한다.