51 大楼轮廓问题
Table of Contents

ac

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


class Node{
    int index;
    int height;

    public Node(int index, int height) {
        this.index = index;
        this.height = height;
    }
}

public class Main {

    public static Scanner sc = new Scanner(System.in);

    static int M = (int) Math.pow(10, 9) + 7;

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));


    public static void main(String[] args) throws Exception {
        int n = Integer.valueOf(reader.readLine());
        List<Node> objList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String line = reader.readLine();
            String[] strArr = line.split(" ");
            int left = Integer.valueOf(strArr[0]);
            int right = Integer.valueOf(strArr[1]);
            int height = Integer.valueOf(strArr[2]);
            objList.add(new Node(left, height));
            objList.add(new Node(right, -height));
        }
        objList.sort( (o1, o2)->{
            // 位置从小到大
            if(o1.index != o2.index){
                return o1.index - o2.index;
            }else {
                // 高度由高到低
                return -(o1.height - o2.height);
            }
        });
        // 存储没有结束绘制的大楼(高度,次数的映射,高度由低到高,lastKey是最高的)
        // 如果lastKey 没有遇到比其更高的左墙,或者 没有遇到其对应的结束
        // 那么 期间遇到的高度比着低的是不能绘制轮廓的
        TreeMap<Integer, Integer> mp = new TreeMap<>();
        List<List<Integer>> res = new ArrayList<>();
        int prePos = 0; // 记录上一次画出轮廓的最右位置
        for(int i=0;i<objList.size();i++){
            int pos = objList.get(i).index;
            int h = objList.get(i).height;
            if(mp.isEmpty()){
                mp.put(h,1);
                prePos = pos;
                continue;
            }
            if(h > 0){ // 左边轮廓
                // 高于没结束的最高的大楼且位置更右
                if(h > mp.lastKey() && pos >= prePos){
                    List<Integer> lunkuo = new ArrayList<>();
                    lunkuo.add(prePos);
                    lunkuo.add(pos);
                    lunkuo.add(mp.lastKey());
                    res.add(lunkuo);
                    prePos = pos;
                }
                // 新增大楼:h可能原来是存在的,这里出现次数加1即可
                mp.put(h, mp.getOrDefault(h, 0) + 1);
            }else { // 右边轮廓
                if(-h == mp.lastKey() && pos >= prePos && mp.get(-h) < 2){
                    List<Integer> lunkuo = new ArrayList<>();
                    lunkuo.add(prePos);
                    lunkuo.add(pos);
                    lunkuo.add(mp.lastKey());
                    res.add(lunkuo);
                    prePos = pos;
                }
                // 删除大楼
                if(mp.containsKey(-h)) {
                    if (mp.get(-h) == 1) {
                        mp.remove(-h);
                    }else if (mp.get(-h) > 1) {
                        mp.put(-h, mp.get(-h) - 1);
                    }
                }
            } 
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<res.size();i++){
            sb.append(res.get(i).get(0) + " " + res.get(i).get(1) + " "
                    + res.get(i).get(2));
            if(i < res.size()){
                sb.append("\n");
            }
        }
        System.out.print(sb.toString());
    }

}
/*
8
2 5 6
1 7 4
4 6 7
3 6 5
10 13 2
9 11 3
12 14 4
10 12 5

1 2 4
2 4 6
4 6 7
6 7 4
9 10 3
10 12 5
12 14 4

eg2:
3
1 3 3
2 4 4
5 6 1

1 2 3
2 4 4
5 6 1

eg3:
3
1 3 3
2 4 3
5 6 1

eg4:
3
1 3 3
1 2 4
5 6 1
 */