Editorial

---

D

summary:

segment가 n개 주어지는데 2개씩 합친 segment(=pair)를 최대한 많이 만들어야 한다.

pair끼리는 서로 intersect하는 부분이 나오면 안되고, pair를 구성하는 두 segment는 intersect해야만 한다.

쓰지 못한 것은 버려지는데, 버려지는 segment의 최솟값을 구하는 문제이다.

solution:

$n$이 2000으로 작기 때문에, 합칠 수 있는(intersect하는) segment를 모두 합쳐서 나올 수 있는 모든 $O(n^2)$개의 pair를 가지고 시작한다.

그 다음에는 회의실배정 문제처럼 뒤에거 기준으로 정렬해서 greedy하게 해결하면 된다.

opinion:

뒤에거 기준으로 정렬해야서 뭘 하면 좋겠다까지는 생각했는데, 모든 pair를 합쳐서 갖고 시작하면 된다는 key idea를 떠올리지 못했다.