먼저 구간들을 구간의 시작점 순으로 정렬하여 순서대로 끝점의 위치를 보며 부분 최장길이 감소수열(순서를 지키며)을 구하면 된다. 이렇게 변형된 문제는, 부분 최장길이 증가수열(longest increasing subsequence) 문제와 동치이다. 부분 최장길이 증가수열 문제는 O(N log N) 시간의 해법이 알려져 있는데 이를 이용하면 O(N log N) 시간에 해를 구할 수 있다.

  이 때 구간의 양끝이 같을 수 있으므로 주의해야 한다. 완전히 같은 구간은 한개만 남겨두고 제거하고, 정렬할 때 구간의 시작 위치가 같으면 긴 것부터 나오도록 하며, 부분 최장길이 감소수열을 구할 때 수열 내에 같은 숫자도 들어갈 수 있다는 점을 유의해야 한다.

  다음과 같은 O(N²) 시간의 동적 계획법 알고리즘을 이용할 수 있는데, 이럴 경우 50점 정도 받을 수 있다.

  D[i]의 정의

     D[i]: i번째 구간이 먹이사슬에 포함되는 제일 작은 구간일 때 최대 사슬길이

  D[i]를  구하는 식

     D[i]: 구간 i를 포함하는 모든 구간 j에 대한 (D[j]+1) 들의 최대값   

  70%의 테스트데이터에는 하나의 구간이 다른 구간에 완전히 포함되든지(두 구간이 같지  않음), 혹은 겹치는 부분이 없든지 중 하나인데, 이러한 테스트데이터에 대해서는 구간의 시작점 순으로 정렬하여 끝점을 기준으로 스택을 이용해 구간이 겹쳐지면 스택에 쌓고, 아니면 가능할 때 까지 pop하는 방식으로 진행하며 최대 스택 높이를 기억하여 출력하는 방식으로 해결할 수 있다.