[BOJ] 13160번: 최대 클리크 구하기

https://www.acmicpc.net/problem/13160

문제에서 요구하는 것은 결국 x = k라는 직선에 겹치는 선분의 최대 갯수입니다. Greedy한 관점에서 생각해보면 이러한 k는 특정 i에 대해 S_i 혹은 E_i와 일치해도 상관없음을 알 수 있습니다.(살짝만 평행이동한다는 관점에서 생각해보면 됩니다.) 그렇다고 해서 모든 S_i, E_i에 대해 전수조사를 무식하게 하면 O(N^2)입니다. 대신 모든 S_i, E_i 점을 위치 순으로 정렬해둔 뒤, 각 점을 위치 순으로 순회하면서 cnt를 1 증가하거나 1 감소하는 방식으로 각 점에서의 cnt 값을 O(1)에 알 수 있습니다.

최댓값을 위와 같이 구한 이후에는 다시 한 번 위치 순으로 순회하면서 i번째 선분이 등장했는지를 Set에 저장함으로서 해결할 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/13160.cpp