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 내부에 포함되는 선의 갯수가 된다.