Scheduling Unit-time tasks with Release time and Deadline

Garey / Johnson의 1981년 논문 "Scheduling Unit-time tasks with Release time and Deadline" 를 읽고 내용을 정리해 보았다. Competitive Programming에서는 2017년 ICPC World Finals에서 한 명도 풀지 못했던 문제인 "Scenery"의 풀이로 유명한 논문이다. 이 글에서는 $O(n^2)$  알고리즘까지만 정리했으며, $O(n\log n)$ 알고리즘은 하지 못했다. ㅠㅠ 

이 문제의 $O(n^2)$ 알고리즘은 매우 아름답다. 혼자 생각하지 못하더라도 보고 배울 가치가 충분하니 일독을 권한다.

201808.pdf

여담 : 예전에 breakun 님이 BOJ 슬랙에 질문했던 문제 중 하나이다. 

$N$개의 구간 $[S_i, T_i]$ 가 주어진다. ($S_i, T_i$는 실수.) 아래 두 조건을 만족하는 $N$개의 실수 $A_i$ 를 찾아라. 

1. $A_i$는 구간 $[S_i, T_i]$ 에 속한다. 즉, $S_i \leq A_i \leq T_i$. 

2. $Min_{i < j}(|A_j - A_i|)$, 다른 말로 최소 갭을 최대화하여라. 

이 문제는 어떻게 해결할까?