building outline

TAG: 扫描线、哈希堆、排序

code

class node {
public:
    int id;
    int num;
    node(int id = 0, int num = 0)
    {
        this->id = id;
        this->num = num;
    }
};

class hashheap {
public:
    vector<int> heap;
    unordered_map<int, node> hash;
    int count;
    int mode;

    hashheap(int mode)
    {
        this->mode = mode;
    }

    int size()
    {
        return count;
    }

    int top()
    {
        return heap[0];
    }

    bool isEmpty()
    {
        return count == 0;
    }

    int parent(int id)
    {
        if(id == 0)
        {
            return -1;
        }
        return (id-1)/2;
    }

    int lson(int id)
    {
        return id*2 + 1;
    }

    int rson(int id)
    {
        return id*2 + 2;
    }

    bool comparesmall(int a, int b)
    {
        if(a <= b)
        {
            if(mode == 0)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            if(mode == 0)
            {
                return false;
            }
            else
            {
                return true;
            }
        }
    }

    void swap(int ida, int idb)
    {
        int vala = heap[ida];
        int valb = heap[idb];

        int numa = hash[vala].num;
        int numb = hash[valb].num;

        hash[vala] = node(idb, numa);
        hash[valb] = node(ida, numb);

        heap[ida] = valb;
        heap[idb] = vala;
    }

    void siftup(int id)
    {
        while(parent(id) != -1)
        {
            int p = parent(id);
            if(comparesmall(heap[p], heap[id]) == true)
            {
                break;
            }
            else
            {
                swap(p, id);
            }
                id = p;
        }
    }

    void siftdown(int id)
    {
        while(lson(id) < heap.size())
        {
            int lid = lson(id);
            int rid = rson(id);
            int son;
            if(rid >= heap.size() || comparesmall(heap[lid], heap[rid]))
            {
                son = lid;
            }
            else
            {
                son = rid;
            }

            if(comparesmall(heap[id], heap[son]))
            {
                break;
            }
            else
            {
                swap(id, son);
            }
                id = son;
        }
    }

    void add(int val)
    {
        count++;
        if(hash.find(val) != hash.end())
        {
            hash[val].num++;
        }
        else
        {
            int idx = heap.size();
            heap.push_back(val);
            hash[val] = node(idx, 1);

            siftup(idx);
        }
    }

    int pop()
    {
        count--;
        int now = heap[0];
        if(hash[now].num > 1)
        {
            hash[now].num--;
        }
        else
        {
            swap(0, heap.size()-1);
            heap.pop_back();
            hash.erase(now);
            if(heap.size() > 0)
            {
                siftdown(0);
            }

        }

        return now;
    }

    void remove(int now)
    {
        count--;
        if(hash[now].num > 1)
        {
            hash[now].num--;
        }
        else
        {
            int idx = hash[now].id;

            swap(idx, heap.size()-1);
            heap.pop_back();
            hash.erase(now);
            if(heap.size() > idx)
            {

                siftdown(idx);
                siftup(idx);
            }
        }
    }
};

class edge {
public:
    int pos;
    int height;
    bool isStart;

    edge(int pos, int height, bool isStart)
    {
        this->pos = pos;
        this->height = height;
        this->isStart = isStart;
    }
};



static bool myCompare(const edge& s1, const edge& s2)
{
    if(s1.pos != s2.pos)
    {
        return s1.pos <= s2.pos;
    }

    // pos == s1.pos

    if(s1.isStart && s2.isStart)
    {
        return s2.height <= s1.height;
    }

    if(!s1.isStart && !s2.isStart)
    {
        return s1.height <= s2.height;
    }

    return s1.isStart;
}


vector<vector<int>> output(vector<vector<int>>& res)
{
    vector<vector<int>> ans;
    if(res.size() <= 0)
    {
        return ans;
    }

    int pre = res[0][0];
    int height = res[0][1];
    for(int i = 1; i<res.size(); i++)
    {
        vector<int> now;
        int id = res[i][0];
        if(height > 0)
        {
            now.push_back(pre);
            now.push_back(id);
            now.push_back(height);
            ans.push_back(now);
        }
        pre = id;
        height = res[i][1];
    }

    return ans;
}


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>> ans;
        if(buildings.size() == 0 || buildings[0].size() == 0)
        {
            return ans;
        }

        vector<edge> edges;
        for(vector<int> building : buildings)
        {
            edge start = edge(building[0], building[2], true);
            edge end = edge(building[1], building[2], false);
            edges.push_back(start);
            edges.push_back(end);
        }

        sort(edges.begin(), edges.end(), myCompare);

        hashheap heap(1);

        int i = 0;
        for(edge ed : edges)
        {
            vector<int> now;
            if(ed.isStart)
            {
                if(heap.isEmpty() || ed.height > heap.top())
                {
                    now.push_back(ed.pos);
                    now.push_back(ed.height);
                    ans.push_back(now);
                }
                heap.add(ed.height);
            }
            else
            {
                heap.remove(ed.height);

                if(heap.isEmpty() || ed.height > heap.top())
                {
                    if(heap.isEmpty())
                    {
                        now.push_back(ed.pos);
                        now.push_back(0);
                    }
                    else
                    {
                        now.push_back(ed.pos);
                        now.push_back(heap.top());
                    }
                    ans.push_back(now);
                }

            }

        }
        return output(ans);
    }
};