大楼轮廓问题

1. 坐标
2. 是否是加入一个高度
3. 大楼高度

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeMap;
import java.util.Map.Entry;

class Node {
    public int x;
    public boolean isAdd;
    public int height;
    public Node(int x, boolean isAdd, int height) {
        this.x = x;
        this.isAdd = isAdd;
        this.height = height;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Node[] buildings = new Node[2 * n];
        Node node;
        for(int i = 0; i < n; i++){
            String[] params = br.readLine().split(" ");
            node = new Node(Integer.parseInt(params[0]), true, Integer.parseInt(params[2]));
            buildings[i] = node;
            node = new Node(Integer.parseInt(params[1]), false, Integer.parseInt(params[2]));
            buildings[i + n] = node;
        }
        Arrays.sort(buildings, new Comparator<Node>() {
            @Override
            public int compare(Node node1, Node node2) {
                return node1.x != node2.x? node1.x - node2.x: node1.isAdd? -1: 1;
            }
        });
        TreeMap<Integer, Integer> mapHeightTimes = new TreeMap<>();
        TreeMap<Integer, Integer> mapXvalueHeight = new TreeMap<>();
        for(int i = 0; i < 2*n; i++){
            if(buildings[i].isAdd){
                mapHeightTimes.put(buildings[i].height, mapHeightTimes.getOrDefault(buildings[i].height, 0) + 1);
            }else{
                if(mapHeightTimes.get(buildings[i].height) == 1){
                    mapHeightTimes.remove(buildings[i].height);
                }else{
                    mapHeightTimes.put(buildings[i].height, mapHeightTimes.get(buildings[i].height) - 1);
                }
            }
            if(mapHeightTimes.isEmpty()){
                mapXvalueHeight.put(buildings[i].x, 0);    // 没有高度了，当前坐标x的最大高度为0
            }else{
                mapXvalueHeight.put(buildings[i].x, mapHeightTimes.lastKey());    // 否则是加入过的最大高度
            }
        }
        int preX = 0, preHeight = 0;
        for(Entry<Integer, Integer> entry: mapXvalueHeight.entrySet()) {
            // 当前位置及其最大高度
            int curX = entry.getKey();
            int curHeight = entry.getValue();
            if(curHeight != preHeight){
                // 高度改变时更新轮廓线
                if(preHeight != 0) System.out.println(preX + " " + curX + " " + preHeight);
                preX = curX;
                preHeight = curHeight;
            }
        }
    }
}

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
    int x;  //所在x下标
    int y;  //所在高度
    int left_or_right;//是一个长方形的 左边=0  右边=1
    node(int _x,int _y,int which)
    {
        x=_x;
        y=_y;
        left_or_right=which;
    }
};
bool static cmp1(node a,node b)
{
    return a.x<b.x;  //关键点left=>right 按照下标排序
}

class my_heap
{
    private:
     priority_queue<int> q1;
     priority_queue<int> q2;  //两个最大堆
    public:
    void push(int _v)
    {
        q1.push(_v);
    }
    void erase(int _v) //任意节点删除
    {
        q2.push(_v);//在待删除堆中插入该值即可
    }
    void pop()  //删除过程 首先
    {
        while(q1.top()==q2.top()) //如果q2的堆顶（那些被任意删除的元素）==q1的堆顶  不断一起弹出
        {
            q1.pop();
            q2.pop();
        }
        q1.pop(); //最后弹出 
    }
    int top()  //获取最大最
    {
        while(q1.empty()==false &&q2.empty()==false && q1.top()==q2.top())
        {
            q1.pop();
            q2.pop();
        }
        if(q1.empty())
            return 0;
        else
            return q1.top();
    }
    bool empty()   //当前堆是否为空
    {
        return q1.size()==0 || q1.size()==q2.size();
    }
};
int main()
{
    int n;
    cin>>n;
    int l,r,h;
    vector<node> node_arr;//存放关键点
    for(int i=0;i<n;i++)
    {
        cin>>l>>r>>h;
        node_arr.push_back(node(l,h,0));
        node_arr.push_back(node(r,h,1));   //每个大楼都有两个关键节点
    }
    sort(node_arr.begin(),node_arr.end(),cmp1);
    //初始化两个最大堆  以支持任意节点的删除
    my_heap skyline;
    int len=node_arr.size();
    int height=0;//当前楼最大高度
    int index=0;//当前最大高度的左起点
    for(int i=0;i<len;i++)  //开始从左往右扫描关键点
    {
        if(node_arr[i].left_or_right==0)  //左边节点
        {
           skyline.push(node_arr[i].y);  //放入最大堆中
           int now_height=skyline.top();//当前的最大高度
            if(now_height>height) //新加入楼更高了
            {
                if(height>0 && node_arr[i].x>index)
                     cout<<index<<" "<<node_arr[i].x<<" "<<height<<endl;//输出前一部分高度
                //同时更新新的区间起点信息
                index=node_arr[i].x;
                height=node_arr[i].y;
                
            }
            
            
        }
        else  //遇到右边关键点
        {
            skyline.erase(node_arr[i].y);//删除该节点
            if(skyline.top()<height)  //若删除之后 天际线变低了
            {
                if(node_arr[i].x>index)
                     cout<<index<<" "<<node_arr[i].x<<" "<<height<<endl;
                //更新区间的起点信息
                index=node_arr[i].x;
                height=skyline.top();
                
            }
        }
    } 
}