PS

백준 13334. 철로

tose33 2023. 4. 17. 14:46

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

 

13334번: 철로

입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0

www.acmicpc.net

 

line sweeping 문제.

 

아이디어는 길이 d의 선 L을 왼쪽에서 오른쪽으로 각 선의 끝점으로 이동시키면서 선의 시작점을 우선순위 큐 (min heap)에 넣고,

우선순위 큐에서 선 L의 시작점보다 작은 시작점은 빼주는 것이다.

이렇게 하면 우선순위 큐의 크기가 선 L 내부에 포함되는 선의 갯수가 된다.