Accepted C++ solution O(nlogn) using MaxHeap.


  • 1
    C

    I am using a max-heap to store the height of any buildings currently being processed. I am also processing each point separately (building start and end points).

    When a building start point is added, I output the coordinate if it is the highest point currently. I also put the line in the heap.

    When a building end point is added, I remove the line from the heap, and output a coordinate if there is no higher point currently. In this case, the point I output is brought down to the next lower level in the heap (if that makes sense).

    In both cases, I have to do some heap bookkeeping (multiple lines may be deleted during any start/end event). However, total over the entire program each line is added and deleted exactly once, and therefore time to add/delete all lines in heap is O(nlogn) for n lines.

    I also have to do a rather clever sort, on the various points, to get some tricky cases to work properly (e.g. when multiple buildings start and/or end at the same x, but have different heights).

    Here is the entire code, which is accepted by OJ:

    enum PtType {START=0, END=1};
    class Solution {
        struct Point {
            int uid;    //unique id (name of the line)
            int ht;     //height
            int x;      //xcrd
            PtType typ; //is this start of building or end
            Point(int u, int h, int xc, PtType t) : uid(u), ht(h), x(xc), typ(t) {}
        };
        struct CompareHeight {
            bool operator () (const Point& lhs, const Point& rhs) {
                return (lhs.ht < rhs.ht);
            }
        };
        typedef priority_queue<Point, vector<Point>, CompareHeight> MaxHtHeap;
        int IDCTR;
        MaxHtHeap htHeap;
        vector<Point> crds;
        vector<pair<int, int>> results;
        vector<bool> lineExists;
        
        //returns all start and end points, sorted by x-crd, then start/end type, then ht
        vector<Point> createPoints(vector<vector<int>>& buildings) {
            IDCTR=0;
            for (vector<int>& data : buildings) {
                crds.push_back(Point(IDCTR, data[2], data[0], START));
                crds.push_back(Point(IDCTR, data[2], data[1], END));
                IDCTR++;
            }
            std::sort(crds.begin(), crds.end(), [] (const Point& lhs, const Point& rhs) -> bool {
                if (lhs.x != rhs.x) {
                    return (lhs.x < rhs.x);     //keep lower x first
                } else if (lhs.typ != rhs.typ) {
                    return (lhs.typ < rhs.typ); //keep start before end
                } else {
                    if (lhs.typ == START /* same as == rhs.typ*/) {
                        return (lhs.ht > rhs.ht);   //keep higher height first
                    } else {
                        return (lhs.ht < rhs.ht);   //keep lower height first
                    }
                }
            });
            return crds;
        }
    
        void adjustHeapBookkeeping() {
            //get topmost non-deleted line in heap
            while (!htHeap.empty() && !lineExists[htHeap.top().uid]) { 
                htHeap.pop();
            }
        }
    
        void handleBuildingStart(Point& pt) {
            adjustHeapBookkeeping();
    
            bool tallest = (htHeap.empty()) ? true : (htHeap.top().ht < pt.ht);
            htHeap.push(pt);
            lineExists[pt.uid] = true;
            if (!tallest) return;
    
            results.push_back(make_pair(pt.x, pt.ht));
            
        }
    
        void handleBuildingEnd(Point& pt) {
            lineExists[pt.uid] = false;
            adjustHeapBookkeeping();
    
            int hthp = (htHeap.empty()) ? 0 : (htHeap.top().ht);
            if (hthp >= pt.ht) return;
    
            results.push_back(make_pair(pt.x, hthp));
        }
    
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            if (buildings.empty()) return vector<pair<int, int>>();
    
            createPoints(buildings);
            lineExists = vector<bool>(IDCTR, false);
    
            for (Point& pt : crds) {
                if (pt.typ == START) { //starting a building's contour
                    handleBuildingStart(pt);
                } else {                //ending a building's contour
                    handleBuildingEnd(pt);
                }
            }
            return results;
        }
    };

  • 0
    M
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.