Loading...
Skyline
Time: 5 s
Memory: 500 MB
You are given a set of buildings in a two-dimensional plane. Each building is represented by a triplet (Li, Ri, Hi), where Li and Ri are the left and right coordinates of the building, and Hi is the height of the building. Buildings may overlap, and you can assume that the left and right coordinates are integers.
Write a program to find the skyline formed by these buildings. The skyline is the outline formed by the top edges of the buildings when viewed from a distance.
 
Input
- The first line contains an integer N (1 <= N <= 10^5),   representing the number of buildings. 
- The next N lines each contain three integers Li, Ri, and Hi representing the left coordinate, right coordinate, and height of the i-th building.
Output
- Print the coordinates of the points where the skyline changes. Each point should be represented as a pair (x, y), where x is the x-coordinate and y is the height of the skyline at that point.
 
Notes
Sample Input Sample Output
4
1 5 2
2 4 5
3 7 3
6 9 1
 
1 2
2 5
4 3
7 1
9 0
 
Problem Info
Problem ID 198
Time Limit 5000 ms
Memory Limit 512000 KB
Moderators Khan , Alom_Shanto
Statistics
Submit
You need to Login or Registration for submit your solution