스카이라인
시간 제한2초메모리 제한128 MB
최대 10만 개 건물이 주어질 때 스위프와 힙을 이용해 병합된 스카이라인의 좌표와 높이 변화 지점들을 출력합니다.
문제
직사각형 모양의 건물 N개가 주어진다. 각 건물은 왼쪽 x좌표 L, 높이 H, 오른쪽 x좌표 R로 표현되며, 모든 건물은 같은 높이의 지면 위에 서 있다.
스카이라인은 이 직사각형들을 모두 합쳤을 때 보이는 바깥 윤곽선이다. 왼쪽에서 오른쪽으로 보면서 높이가 바뀌는 모든 지점을 구하라.
입력
첫째 줄에 건물의 개수 N(1 <= N <= 100,000)이 주어진다.
다음 N개의 줄에는 건물 하나를 나타내는 세 정수 L, H, R이 주어진다. L은 왼쪽 x좌표, H는 높이, R은 오른쪽 x좌표를 뜻한다.
각 값은 1 <= L < R <= 1,000,000,000, 1 <= H <= 1,000,000,000을 만족한다.
출력
스카이라인을 한 줄에 출력한다. 높이가 변하는 각 지점마다 그 지점의 x좌표와 그 지점부터의 높이를 차례로 출력한다. 모든 값은 공백으로 구분한다.