백준 1689. 겹치는 선분

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

1689번: 겹치는 선분

 

 

e 기준 min-hape 인 priority queue 를 만든다.

 

모든 선분들을 s 기준 오름차순 정렬한다.

 

오름차순 정렬한 선분들을 하나씩 순회하는데,

새로운 선분을 탐색할때 만약 pq.top 의 끝나는 좌표 e 보다, 새로운 선분의 s가 크거나 같다면 pq.top() 에 있는 선분은 더이상 겹쳐지지 않는다는 뜻이므로 pop 해준다.

 

따라서 pq의 사이즈가 곧 겹쳐져 있는 선분의 갯수가 되기 때문에 pq.size() 의 가장 큰 값이 답이 된다.