백준 13334 철로

정렬(sort)과 우선순위큐(priority_queue)를 이용해서 풀 수 있다.
입력으로 들어온 집-사무실(사무실-집일 수도 있음, 주의) 구간을 s - e라고 하면 e를 기준으로 sorting하고 앞에서부터 보면서 주어진 범위 d만큼에 몇개가 포함되는지 체크해 나가면 되는데, 그냥 일일이 다 보면 O(N^2)이 된다.
그래서 우선순위큐(여기서 사용할 것은 최소힙)를 이용한다.
정렬된 구간을 앞에서부터 보면서 우선순위큐에도 구간의 s값을 넣는다. 그리고 우선순위 큐에서 가장 위쪽(top)에 해당하는 값을 보면서 e - d안쪽으로 들어와 있는지 보고, 포함되어 있지 않다면 우선순위 큐에서 pop한다.

범위는 d로 고정되어 있고, e의 크기대로 정렬한 상태이기 때문에,
어떤 구간이 앞쪽의 e에서 봤을 때 d만큼의 범위에 포함되지 않는다면 뒤쪽의 e에서 봐도 그 구간은 d만큼의 범위에 포함되지 않을 것이므로 빼도 되고, 해당 구간 e까지의 (범위 d만큼)포함되는 구간의 수는 그 시점에서 우선순위 큐에 들어있는 구간의 개수가 된다.

시간복잡도는 O(NlogN)이 되는 것 같다.