[문제 요약] 왼쪽 단자와 오른쪽 단자를 선 끼리 교차하지 않고 연결하고자 한다.
아래 그림은 왼쪽단자에서 오른쪽 단자로 4 , 6 , 3 , 1 , 5 로 연결된 상태를 나타낸다.
문제는 서로 교차하지 않게 최대한 많은 단자를 연결하는 것이다. 이 경우 아래 그림일 때가 최대로 연결 가능한 상태이다.
입력 6 4 2 6 3 1 5 출력 3 입력 10 2 3 4 5 6 7 8 9 10 1 출력 9 입력 8 8 7 6 5 4 3 2 1 출력 1 입력 9 5 8 9 2 3 1 7 4 6 출력 4
출처: Northwestern Europe 2003