data_structure_algorithm/algorithm/code/building_outline.cpp at master · T-tssxuan/data_structure_algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

/**
 * Describe:
 * Merge the pairs [start_point, end_point, heighht], with the highers covers
 * the lower when the range overlapped.
 */


class Solution {
public:
    vector<vector<int> > buildingOutline(vector<vector<int> > &buildings) {
        vector<vector<int>> result;
        // The start point of the heap
        size_t start = 0;
        // The end point of the heap
        size_t end = buildings.size();
        vector<int> tmp {0, 0, 0};

        // the compare function
        auto compare = [](vector<int>& vec1, vector<int>& vec2) {
            return !(vec1[0] < vec2[0]);
        };
        // make the buildings vector becomes a min heap
        make_heap(buildings.begin() + start, buildings.begin() + end, compare);

        // get all element in the heap
        while (start < end) {
            // get the minest element in the heap
            pop_heap(buildings.begin() + start, buildings.begin() + end, compare);

            if (tmp[2] == 0) {
                // if result empty just skip
                tmp = buildings[end - 1];
                end--;
            } else if (tmp[2] == buildings[end - 1][2]){
                // the height of the newer equals the tail
                if (tmp[1] >= buildings[end - 1][0]) {
                    // overlapped: update the range
                    tmp[1] = tmp[1] > buildings[end - 1][1]? \
                             tmp[1] : buildings[end - 1][1];
                } else {
                    // no overlap, push to result and continue
                    push_result(result, tmp);
                    tmp = buildings[end - 1];
                }
                end--;
            } else if (tmp[2] < buildings[end - 1][2]) {
                // the height of the newer higher than the tail
                if (tmp[1] <= buildings[end - 1][1]) {
                    tmp[1] = tmp[1] < buildings[end - 1][0]? \
                             tmp[1] : buildings[end - 1][0];
                    push_result(result, tmp);

                    tmp = buildings[end - 1];
                    end--;
                } else {
                    int tmp_end = tmp[1];
                    int tmp_hight = tmp[2];

                    tmp[1] = buildings[end - 1][0];
                    push_result(result, tmp);

                    tmp = buildings[end - 1];
                    buildings[end - 1][0] = buildings[end - 1][1];
                    buildings[end - 1][1] = tmp_end;
                    buildings[end - 1][2] = tmp_hight;
                    push_heap(buildings.begin() + start, buildings.begin() + end, compare);
                }
            } else if (tmp[2] > buildings[end - 1][2]) {
                // the height of the newer lower than the tail
                if (tmp[1] >= buildings[end - 1][1]) {
                    end--;
                } else if (tmp[1] <= buildings[end - 1][0]) {
                    push_result(result, tmp);
                    tmp = buildings[end - 1];
                    end--;
                } else {
                    buildings[end - 1][0] = tmp[1];
                    push_heap(buildings.begin() + start, buildings.begin() + end, compare);
                }
            }
        }
        if (tmp[2]) {
            result.push_back(tmp);
        }
        return result;
    }
    void push_result(vector<vector<int>>& result, vector<int>& tmp) {
        // process the new result
        if (tmp[0] != tmp[1]) {
            // with range greater than 0
            if (result.size() && result.back()[2] == tmp[2]
                    && result.back()[1] == tmp[0]) {
                // duplicated with the previous result
                result.back()[1] = tmp[1];
            } else {
                // the brand new one
                result.push_back(tmp);
            }
        }
    }

};

/**
 * Input: a N with N * 3 number
 * Ouput: [start_point, end_point, height] each row
 */
int main() {
    Solution so;
    vector<vector<int>> test;
    int n;
    vector<int> unit(3, 0);
    while (cin >> n) {
        test.clear();
        while (n-- > 0) {
            for (int i = 0; i < 3; i++) {
                cin >> unit[i];
            }
            test.push_back(unit);
        }
        auto re = so.buildingOutline(test);
        for (auto& ele : re) {
            cout << "[";
            cout << ele[0] << "," << ele[1] << "," << ele[2];
            cout << "]" << endl;
        }
        cout << endl;
    }
    return 0;
}