가중 interval DP의 최댓값만 저장한 표에서 실제 선택 구간을 복원하려면 어떤 정보를 비교해야 하나요?

j에서 현재 구간을 선택한 후보 weight[j] + OPT(p(j))와 건너뛴 후보 OPT(j-1)를 다시 비교합니다. 선택 후보가 크면 j를 결과에 기록하고 j=p(j)로 이동하고, 그렇지 않으면 j를 선택하지 않고 j-1로 이동합니다. 마지막에 역순으로 쌓인 구간을 뒤집으면 finish 순서의 실제 스케줄을 얻습니다.

예를 들어 OPT(4)=14, OPT(3)=10, weight[4]=4, p(4)=3이면 선택 후보는 14, skip 후보도 10이므로 4를 선택합니다. 반면 OPT(5)=14, 선택 후보가 13이면 5를 건너뛰고 4로 내려갑니다. 선택한 뒤 j-1이 아니라 p(j)로 점프하는 이유는 j와 겹치는 구간들을 모두 제외한 호환 prefix만 다음 문제로 남겨야 하기 때문입니다.

동률은 별도 출력 계약입니다. take > skip으로 작성하면 동률에서 skip을 우선해 결정적인 한 해를 반환하고, take >= skip이면 선택을 우선할 수 있습니다. 둘 다 최댓값을 유지하지만, 재현 가능한 출력이나 사용자 선호가 필요하면 정책을 고정해야 합니다. parent 비트를 미리 저장하면 복원 때 식을 재계산하지 않아도 되지만, OPT와 p만으로도 복원은 가능합니다.

복원 시 값이 같은 경우도 유효성 검사를 해야 합니다. 예를 들어 take=10, skip=10이면 take >= skip 정책은 j를 선택하고 p(j)로 이동하며, take > skip 정책은 j를 건너뛰고 j-1로 갑니다. 어느 쪽도 값은 10이지만 반환 작업 ID가 달라질 수 있습니다. 선택된 인덱스를 역순 stack에 넣은 뒤 뒤집고, 원래 ID를 출력하며, 인접 구간의 finish≤start를 다시 검사하면 정렬 인덱스와 실제 작업 ID의 매핑 오류를 잡을 수 있습니다.