218. The Skyline Problem Hard

1/**
2 * [218] The Skyline Problem
3 *
4 * A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.
5 * The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:
6 * 
7 * 	lefti is the x coordinate of the left edge of the i^th building.
8 * 	righti is the x coordinate of the right edge of the i^th building.
9 * 	heighti is the height of the i^th building.
10 * 
11 * You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
12 * The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.
13 * Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3],[4 5],[7 5],[11 5],[12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2 3],[4 5],[12 7],...]
14 *  
15 * Example 1:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2020/12/01/merged.jpg" style="width: 800px; height: 331px;" />
17 * Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
18 * Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
19 * Explanation:
20 * Figure A shows the buildings of the input.
21 * Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.
22 * 
23 * Example 2:
24 * 
25 * Input: buildings = [[0,2,3],[2,5,3]]
26 * Output: [[0,3],[5,0]]
27 * 
28 *  
29 * Constraints:
30 * 
31 * 	1 <= buildings.length <= 10^4
32 * 	0 <= lefti < righti <= 2^31 - 1
33 * 	1 <= heighti <= 2^31 - 1
34 * 	buildings is sorted by lefti in non-decreasing order.
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/the-skyline-problem/
40// discuss: https://leetcode.com/problems/the-skyline-problem/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn get_skyline(buildings: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
46        vec![]
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_218() {
58    }
59}
60