<repo_name>hktwarzone/LintCode<file_sep>/399.cpp
/*
Nuts & Bolts Problem 
Given a set of n nuts of different sizes and n bolts of different sizes. 
There is a one-one mapping between nuts and bolts. Comparison of a nut to another nut or a bolt to another bolt is not allowed. 
It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

We will give you a compare function to compare nut with bolt.

Example
Given nuts = ['ab','bc','dd','gg'], bolts = ['AB','GG', 'DD', 'BC'].
Your code should find the matching bolts and nuts.
one of the possible return:
nuts = ['ab','bc','dd','gg'], bolts = ['AB','BC','DD','GG'].
we will tell you the match compare function. If we give you another compare function.
the possible return is the following:
nuts = ['ab','bc','dd','gg'], bolts = ['BC','AA','DD','GG'].
So you must use the compare function that we give to do the sorting.
The order of the nuts or bolts does not matter. You just need to find the matching bolt for each nut.
*/

/**
 * class Comparator {
 *     public:
 *      int cmp(string a, string b);
 * };
 * You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
 * if "a" is bigger than "b", it will return 1, else if they are equal,
 * it will return 0, else if "a" is smaller than "b", it will return -1.
 * When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
class Solution {
public:
    /**
     * @param nuts: a vector of integers
     * @param bolts: a vector of integers
     * @param compare: a instance of Comparator
     * @return: nothing
     */
    void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare) {
        // write your code here
        if (nuts.size() != bolts.size()) return;
        cmpsort(nuts, bolts, 0, nuts.size() - 1, compare);
    }
private:
    void cmpsort(vector<string>& n, vector<string>& b, int start, int end, Comparator compare) {
        if (start >= end) return;
        int mid = start + (end - start) / 2;
        string pivot = b[mid];
        int left = start;
        int right = end;
        while(true) {
            while (left < right && compare.cmp(n[left], pivot) < 0) { left++; }
            while (left < right && compare.cmp(n[right], pivot) > 0) { right--; }
            if (left < right) {
                swap(n[left], n[right]);
            }
            else { break; }
        }
        pivot = n[right];
        left = start;
        right = end;
        while(true) {
            while (left < right && compare.cmp(pivot, b[left]) > 0) { left++; }
            while (left < right && compare.cmp(pivot, b[right]) < 0) { right--; }
            if (left < right) {
                swap(b[left], b[right]);
            }
            else { break; }
        }
        cmpsort(n, b, start, right - 1, compare);
        cmpsort(n, b, right + 1, end, compare);
    }
};
<file_sep>/434.cpp
/*
Number of Islands II
Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). 
Originally, the 2D matrix is all 0 which means there is only sea in the matrix. 
The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the 
grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.

Example
Given n = 3, m = 3, array of pair A = [(0,0),(0,1),(2,2),(2,1)].

return [1,1,2,2].

Note
0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. 
We only consider up/down/left/right adjacent.
*/

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    /**
     * @param n an integer
     * @param m an integer
     * @param operators an array of point
     * @return an integer array
     */
    vector<int> numIslands2(int n, int m, vector<Point>& operators) {
        // Write your code here
        int t = operators.size();
        vector<int> numI;
        vector<vector<int>> board(n, vector<int>(m, 0));
        vector<int> father(n * m, 0);
        for (int i = 0; i < n * m; i++) {
            father[i] = i;
        }
        int dx[4] = {1,0,-1,0};
        int dy[4] = {0,1,0,-1};
        int res = 0;
        for (int i = 0; i < t; i++) {
            int ox = operators[i].x;
            int oy = operators[i].y;
            int ido = id(m, ox, oy);
            board[ox][oy] = 1;
            res++;
            for (int j = 0; j < 4; j++) {
                int nx = ox + dx[j];
                int ny = oy + dy[j];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == 1) {
                    int idd = id(m, nx, ny);
                    int of = compressed_find(father, ido);
                    int nf = compressed_find(father, idd);
                    if (of != nf) {
                        res--;
                        find_union(father, ido, idd);
                    }
                }
            }
            numI.push_back(res);
        }
        return numI;
    }
private:
    int id(int& m, int x, int y) {
        return x * m + y;
    }
    int compressed_find(vector<int>& father, int x) {
        int parent = father[x];
        while(parent != father[parent]) {
            parent = father[parent];
        }
        int tmp = -1;
        int fa = father[x];
        while(fa != father[fa]) {
            tmp = father[fa];
            father[fa] = parent;
            fa = tmp;
        }
        return parent;
    }
    void find_union(vector<int>& father, int x, int y) {
        int fx = compressed_find(father, x);
        int fy = compressed_find(father, y);
        if (fx != fy) {
            father[fx] = fy;
        }
    }
};
<file_sep>/401.cpp
/*
Kth Smallest Number in Sorted Matrix

Find the kth smallest number in at row and column sorted matrix.

Have you met this question in a real interview? Yes
Example
Given k = 4 and a matrix:

[
  [1 ,5 ,7],
  [3 ,7 ,8],
  [4 ,8 ,9],
]
return 5

Challenge
O(k log n), n is the maximal number in width and height.
*/

class Node {
public:
    int x;
    int y;
    int v;
    Node(int xx, int yy, int vv) {
        x = xx;
        y = yy;
        v = vv;
    }
};

class CompareNode {
public:
    bool operator()(Node& n1, Node& n2) {
        return (n1.v > n2.v);
    }
};

class Solution {
public:
    /**
     * @param matrix: a matrix of integers
     * @param k: an integer
     * @return: the kth smallest number in the matrix
     */
    int kthSmallest(vector<vector<int> > &matrix, int k) {
        // write your code here
        if (matrix.empty() || matrix[0].empty()) return -1;
        if (k == 1) return matrix[0][0];
        int n = matrix.size();
        int m = matrix[0].size();
        priority_queue<Node, vector<Node>, CompareNode> q;
        set<pair<int, int>> visited;
        q.push(Node(0, 0, matrix[0][0]));
        visited.insert(make_pair(0, 0));
        int dx[4] = {1,0,-1,0};
        int dy[4] = {0,1,0,-1};
        for (int i = 0; i < k - 1; i++) {
            Node curr = q.top();
            q.pop();
            for (int j = 0; j < 4; j++) {
                int nx = curr.x + dx[j];
                int ny = curr.y + dy[j];
                if (inBound(nx, ny, n, m) && visited.find(make_pair(nx, ny)) == visited.end()) {
                    visited.insert(make_pair(nx, ny));
                    q.push(Node(nx, ny, matrix[nx][ny]));
                }
            }
        }
        return q.top().v;
    }
private:
    bool inBound(int& nx, int& ny, int& n, int& m) {
        return (nx >= 0 && ny >= 0 && nx < n && ny < m);
    }
};
<file_sep>/435.cpp
/*
Post Office Problem
On one line there are n houses. Give you an array of integer means the the position of each house. 
Now you need to pick k position to build k post office, so that the sum distance of each house to the nearest post office 
is the smallest. Return the least possible sum of all distances between each village and its nearest post office.

Example
Given array a = [1,2,3,4,5], k = 2. return 3.

Challenge
Could you solve this problem in O(n^2) time ?
*/

class Solution {
public:
    /**
     * @param A an integer array
     * @param k an integer
     * @return an integer
     */
    int postOffice(vector<int>& A, int k) {
        // Write your code here
        int n = A.size();
        if (n == 0 || k >= n) return 0;
        sort(A.begin(), A.end());
        vector<vector<int>> dis(n + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int mid = i + (j - i) / 2;
                for (int x = i; x <= j; x++) {
                    dis[i][j] += abs(A[x - 1] - A[mid - 1]);
                }
            }
        }
        vector<vector<int>> f(n + 1, vector<int>(k + 1, 0));
        for (int i = 1; i <= n; i++) {
            f[i][1] = dis[1][i];
        }
        for (int j = 2; j <= k; j++) {
            for (int i = j; i <= n; i++) {
                f[i][j] = f[1][j - 1] + dis[2][i];
                for (int x = 2; x < i; x++) {
                    f[i][j] = min(f[i][j], f[x][j - 1] + dis[x + 1][i]);
                }
            }
        }
        return f[n][k];
    }
};
<file_sep>/390.cpp
/*
Find Peak Element II
There is an integer matrix which has the following features:

The numbers in adjacent positions are different.
The matrix has n rows and m columns.
For all i < m, A[0][i] < A[1][i] && A[n - 2][i] > A[n - 1][i].
For all j < n, A[j][0] < A[j][1] && A[j][m - 2] > A[j][m - 1].
We define a position P is a peek if:

A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1]
Find a peak element in this matrix. Return the index of the peak.

Have you met this question in a real interview? Yes
Example
Given a matrix:

[
  [1 ,2 ,3 ,6 ,5],
  [16,41,23,22,6],
  [15,17,24,21,7],
  [14,18,19,20,10],
  [13,14,11,10,9]
]
return index of 41 (which is [1,1]) or index of 24 (which is [2,2])

Note
The matrix may contains multiple peeks, find any of them.

Challenge
Solve it in O(n+m) time.

If you come up with an algorithm that you thought it is O(n log m) or O(m log n), 
can you prove it is actually O(n+m) or propose a similar but O(n+m) algorithm?
*/

class Solution {
public:
    /**
     * @param A: An integer matrix
     * @return: The index of the peak
     */
    vector<int> findPeakII(vector<vector<int> > A) {
        // write your code here
        vector<int> res;
        if (A.empty() || A[0].empty()) return res;
        int n = A.size();
        int m = A[0].size();
        int left = 1;
        int right = n - 2;
        int local = 0;
        while(left < right) {
            int mid = left + (right - left) / 2;
            local = findPeak(A[mid]);
            if (A[mid][local] < A[mid - 1][local]) {
                right = mid - 1;
            }
            else if (A[mid][local] < A[mid + 1][local]) {
                left = mid + 1;
            }
            else {
                res.push_back(mid);
                res.push_back(local);
                return res;
            }
        }
        res.push_back(left);
        res.push_back(findPeak(A[left]));
        return res;
    }
private:
    int findPeak(vector<int>& A) {
        int m = A.size();
        int left = 1;
        int right = m - 2;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] < A[mid - 1]) {
                right = mid - 1;
            }
            else if (A[mid] < A[mid + 1]) {
                left = mid + 1;
            }
            else return mid;
        }
        return left;
    }
};
<file_sep>/360_multimap.cpp
/*
Sliding Window Median
Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, 
find the median of the element inside the window at each moving. 
(If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )
Example
For array [1,2,7,8,5], moving window size k = 3. return [2,7,7]
At first the window is at the start of the array like this
[ | 1,2,7 | ,8,5] , return the median 2;
then the window move one step forward.
[1, | 2,7,8 | ,5], return the median 7;
then the window move one step forward again.
[1,2, | 7,8,5 | ], return the median 7;
Challenge
O(nlog(n)) time
*/

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of the element inside the window at each moving
     */
    vector<int> medianSlidingWindow(vector<int> &nums, int k) {
        // write your code here
        multiset<int, less<int>> minHeap;
        multiset<int, greater<int>> maxHeap;
        vector<int> res;
        for (int i = 0; i < nums.size(); i++) {
            if (i >= k) {
                int toDelete = nums[i - k];
                if (maxHeap.find(toDelete) != maxHeap.end()) {
                    maxHeap.erase(maxHeap.find(toDelete));
                    if (minHeap.size() > maxHeap.size()) {
                        maxHeap.emplace(*minHeap.begin());
                        minHeap.erase(minHeap.begin());
                    }
                }
                else {
                    minHeap.erase(minHeap.find(toDelete));
                    if (maxHeap.size() > 1 + minHeap.size()) {
                        minHeap.emplace(*maxHeap.begin());
                        maxHeap.erase(maxHeap.begin());
                    }
                }
            }
            
            if (maxHeap.empty() || nums[i] <= *(maxHeap.begin())) {
                maxHeap.emplace(nums[i]);
                if (maxHeap.size() > 1 + minHeap.size()) {
                    minHeap.emplace(*maxHeap.begin());
                    maxHeap.erase(maxHeap.begin());
                }
            }
            else {
                minHeap.emplace(nums[i]);
                if (minHeap.size() > maxHeap.size()) {
                    maxHeap.emplace(*minHeap.begin());
                    minHeap.erase(minHeap.begin());
                }
            }
            
            if (i >= k - 1) {
                res.push_back(*maxHeap.begin());
            }
        }
        return res;
    }
};
<file_sep>/360_map.cpp
/*
Sliding Window Median
Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, 
find the median of the element inside the window at each moving. 
(If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

Example
For array [1,2,7,8,5], moving window size k = 3. return [2,7,7]
At first the window is at the start of the array like this
[ | 1,2,7 | ,8,5] , return the median 2;
then the window move one step forward.
[1, | 2,7,8 | ,5], return the median 7;
then the window move one step forward again.
[1,2, | 7,8,5 | ], return the median 7;

Challenge
O(nlog(n)) time
*/

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of the element inside the window at each moving
     */
    vector<int> medianSlidingWindow(vector<int> &nums, int k) {
        // write your code here
        map<int, int> maxHeap;
        map<int, int> minHeap;
        int maxCount = 0;
        int minCount = 0;
        vector<int> res;
        
        for (int i = 0; i < nums.size(); i++) {
            if (i >= k) {
                int toDelete = nums[i - k];
                if (maxHeap.find(toDelete) != maxHeap.end()) {
                    if (maxHeap[toDelete] == 1) {
                        maxHeap.erase(maxHeap.find(toDelete));
                    }
                    else {
                        maxHeap[toDelete]--;
                    }
                    maxCount--;
                }
                else {
                    if (minHeap[toDelete] == 1) {
                        minHeap.erase(minHeap.find(toDelete));
                    }
                    else {
                        minHeap[toDelete]--;
                    }
                    minCount--;
                    
                }
                rebalance(maxHeap, minHeap, maxCount, minCount);
            }
            
            if (maxCount == 0 || nums[i] <= maxHeap.rbegin()->first) {
                maxHeap[nums[i]]++;
                maxCount++;
            }
            else {
                minHeap[nums[i]]++;
                minCount++;
            }
            rebalance(maxHeap, minHeap, maxCount, minCount);
            
            if (i >= k - 1) {
                res.push_back(maxHeap.rbegin()->first);
            }
        }
        return res;
    }
    
private:
    void rebalance(map<int, int>& maxHeap, map<int, int>& minHeap, int& maxCount, int& minCount) {
        if (maxCount < minCount) {
            int target = minHeap.begin()->first;
            if (minHeap[target] == 1) {
                minHeap.erase(minHeap.find(target));
            }
            else {
                minHeap[target]--;
            }
            minCount--;
            maxHeap[target]++;
            maxCount++;
        }
        if (maxCount > minCount + 1) {
            int target = maxHeap.rbegin()->first;
            if (maxHeap[target] == 1) {
                maxHeap.erase(maxHeap.find(target));
            }
            else {
                maxHeap[target]--;
            }
            maxCount--;
            minHeap[target]++;
            minCount++;
        }
            
    }
};
<file_sep>/061.cpp
/*
Search for a Range
Given a sorted array of n integers, find the starting and ending position of a given target value.

If the target is not found in the array, return [-1, -1].

Have you met this question in a real interview? Yes
Example
Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

Challenge
O(log n) time.
*/

class Solution {
    /** 
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
public:
    vector<int> searchRange(vector<int> &A, int target) {
        // write your code here
        int lb = lowerBound(A, target);
        int ub = upperBound(A, target);
        if (lb == ub) return vector<int>{-1, -1};
        else return {lb, ub - 1};
    }
private:
    int lowerBound(vector<int> &A, int target) {
        if (A.empty()) {return -1;}
        if (A[A.size() - 1] < target) {return A.size();}
        if (A[0] >= target) {return 0;}
        int left = 0;
        int right = A.size() - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] >= target) {right = mid;}
            else {left = mid + 1;}
        }
        return left;
    }
    int upperBound(vector<int> &A, int target) {
        if (A.empty()) {return -1;}
        if (A[A.size() - 1] <= target) {return A.size();}
        if (A[0] > target) {return 0;}
        int left = 0;
        int right = A.size() - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] > target) {right = mid;}
            else {left = mid + 1;}
        }
        return left;
    }
};
<file_sep>/403.cpp
/*
Continuous Subarray Sum II
Given an integer array, find a continuous rotate subarray where the sum of numbers is the biggest. 
Your code should return the index of the first number and the index of the last number. 
(If their are duplicate answer, return anyone. The answer can be rorate array or non- rorate array)

Example
Give [3, 1, -100, -3, 4], return [4,1].
*/

class Solution {
public:
    /**
     * @param A an integer array
     * @return  A list of integers includes the index of 
     *          the first number and the index of the last number
     */
    vector<int> continuousSubarraySumII(vector<int>& A) {
        // Write your code here
        vector<int> res;
        if (A.empty()) return res;
        int start = 0;
        int maxsum = A[0];
        int sum = A[0];
        int total = A[0];
        vector<int> resmax = {0, 0};
        vector<int> resmin = {0, 0};
        for (int i = 1; i < A.size(); i++) {
            if (sum < 0) {
                sum = 0;
                start = i;
            }
            sum += A[i];
            total += A[i];
            if (sum > maxsum) {
                maxsum = sum;
                resmax = {start, i};
            }
        }
        int minsum = A[0];
        sum = A[0];
        start = 0;
        for (int i = 1; i < A.size(); i++) {
            if (sum > 0) {
                sum = 0;
                start = i;
            }
            sum += A[i];
            if (sum < minsum) {
                minsum = sum;
                resmin = {start, i};
            }
        }   
        if (total == minsum) {
            return resmax;
        }
        else if (total - minsum <= maxsum) {
            return resmax;
        }
        else { //do not need to handle boundary: if minsum is on the bourdary, total-minsum <= maxsum
            return vector<int>{++resmin[1],--resmin[0]};
        }
    }
};
<file_sep>/011.cpp
/*
Search Range in Binary Search Tree

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.

Have you met this question in a real interview? Yes
Example
If k1 = 10 and k2 = 22, then your function should return [12, 20, 22].

    20
   /  \
  8   22
 / \
4   12
*/

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of the binary search tree.
     * @param k1 and k2: range k1 to k2.
     * @return: Return all keys that k1<=key<=k2 in ascending order.
     */
    vector<int> searchRange(TreeNode* root, int k1, int k2) {
        // write your code here
        vector<int> results;
        if (root == NULL) return results;
        searchHelper(root, k1, k2, results);
        return results;
    }
private:
    void searchHelper(TreeNode* root, int& k1, int& k2, vector<int>& results){
        if (root == NULL) return;
        searchHelper(root->left, k1, k2, results);
        if (k1 <= root->val && root->val <= k2) {
            results.push_back(root->val);
        }    
        searchHelper(root->right, k1, k2, results);
    }
};
<file_sep>/391.cpp
/*
Number of Airplanes in the Sky

Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

Have you met this question in a real interview? Yes
Example
For interval list [[1,10],[2,3],[5,8],[4,7]], return 3

Note
If landing and flying happens at the same time, we consider landing should happen at first.
*/
/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
class Solution {
public:
    /**
     * @param intervals: An interval array
     * @return: Count of airplanes are in the sky.
     */
    int countOfAirplanes(vector<Interval> &airplanes) {
        // write your code here
        vector<pair<int, int>> times;
        for (int i = 0; i < airplanes.size(); i++) {
            times.push_back(make_pair(airplanes[i].start, 1));
            times.push_back(make_pair(airplanes[i].end, -1));
        }
        int res = 0;
        int count = 0;
        sort(times.begin(), times.end());
        for (int i = 0; i < times.size(); i++) {
            count += times[i].second;
            res = max(res, count);
        }
        return res;
    }
};
<file_sep>/364.cpp
/*
Trapping Rain Water II

Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, 
compute how much water it is able to trap after raining.

Example
Given 5*4 matrix

[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]
return 14.

*/

class Node {
public:
    int x;
    int y;
    int h;
    Node(int xx, int yy, int hh) {
        x = xx;
        y = yy;
        h = hh;
    }
};

class CompareNode {
public:
    bool operator()(Node& n1, Node& n2) {
        return (n1.h > n2.h);
    }
};

class Solution {
public:
    /**
     * @param heights: a matrix of integers
     * @return: an integer
     */
    int trapRainWater(vector<vector<int> > &heights) {
        // write your code here
        if (heights.empty() || heights[0].empty()) return 0;
        int n = heights.size();
        int m = heights[0].size();
        priority_queue<Node, vector<Node>, CompareNode> q;
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        for (int i = 0; i < m; i++) {
            q.push(Node(0, i, heights[0][i]));
            q.push(Node(n - 1, i, heights[n - 1][i]));
            visited[0][i] = true;
            visited[n - 1][i] = true;
        }
        for (int i = 0; i < n; i++) {
            q.push(Node(i, 0, heights[i][0]));
            q.push(Node(i, m - 1, heights[i][m - 1]));
            visited[i][0] = true;
            visited[i][m - 1] = true;
        }
        vector<int> dx = {1, 0, -1, 0};
        vector<int> dy = {0, 1, 0, -1};
        int res = 0;
        while(!q.empty()) {
            Node curr_node = q.top();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int curr_x = curr_node.x + dx[i];
                int curr_y = curr_node.y + dy[i];
                if (curr_x >= 0 && curr_x < n && curr_y >= 0 && curr_y < m && !visited[curr_x][curr_y]) {
                    visited[curr_x][curr_y] = true;
                    q.push(Node(curr_x, curr_y, max(curr_node.h, heights[curr_x][curr_y])));
                    res += max(0, curr_node.h - heights[curr_x][curr_y]);
                }
            }
        }
        return res;
    }
};
<file_sep>/131.cpp
/*
Building Outline
Given N buildings in a x-axis，each building is a rectangle and can be represented by a triple (start, end, height)，
where start is the start position on x-axis, end is the end position on x-axis and height is the height of the building. 
Buildings may overlap if you see them from far away，find the outline of them。

An outline can be represented by a triple, (start, end, height), where start is the start position on x-axis of the outline, 
end is the end position on x-axis and height is the height of the outline.

Example
Given 3 buildings：

[
  [1, 3, 3],
  [2, 4, 4],
  [5, 6, 1]
]
The outlines are：

[
  [1, 2, 3],
  [2, 4, 4],
  [5, 6, 1]
]
Note
Please merge the adjacent outlines if they have the same height and make sure different outlines cant overlap on x-axis.

*/

class Solution {
public:
    /**
     * @param buildings: A list of lists of integers
     * @return: Find the outline of those buildings
     */
    vector<vector<int> > buildingOutline(vector<vector<int> > &buildings) {
        // write your code here
        vector<vector<int>> res;
        if (buildings.empty()) return res;
        vector<pair<int, int>> points;
        multiset<int> heights;
        for (int i = 0; i < buildings.size(); i++) {
            points.push_back(make_pair(buildings[i][0], -buildings[i][2]));
            points.push_back(make_pair(buildings[i][1], buildings[i][2]));
        }
        sort(points.begin(), points.end());
        heights.insert(0);
        int currHeight = 0;
        int prevHeight = 0;
        int prevStart = -1;
        for (int i = 0; i < points.size(); i++) {
            if (points[i].second < 0) { heights.insert(-points[i].second); }
            else { heights.erase(heights.find(points[i].second)); }
            currHeight = *heights.rbegin();
            if (prevHeight != currHeight) {
                if (prevStart != -1 && prevHeight > 0) {
                    res.push_back(vector<int>{prevStart, points[i].first, prevHeight});
                }
                prevStart = points[i].first;
                prevHeight = currHeight;
            }
        }
        return res;
    }
};
