地平線の問題の解説

ビルによって出来たシルエットの地平線のスタート地点の座標
(線分の左側の点)を求めること。　本文: <a href="https://leetcode.com/problems/the-skyline-problem/description/">218問題リンク</a>
例えばインプット(A)[x入口, x出口, 高度]:
　　buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]。
求められたアウトプット(Bにある赤い点)[x,y]：
　　res=[[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]。

![merged.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3589185/5f1724e6-bdd9-4c94-a0cc-55d45aae59b5.jpeg)

---
アプローチは全てのビルのx(縦線)を使って、水平線らと直交し、最大高度が
 持つ水平線の高度yを探し出す。現在の高度yが高度リストhの最大値より高い、つまり新たな高度が見つかった場合、その座標を結果リストresに入れる。一度使われた高度は二度と使う必要がないため（お題より水平線のスタート地点の座標しかいらない）、水平線の出口高度yをマイナスにし(-は識別子の役割として、その高度からの離脱を宣言、つまり階段一段を下りる)
 
---
出口がマイナスになったlinesの座標リスト
![SkylineProblemPairs.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3589185/c9f9f8e2-feb6-4dc9-b1cd-efdbbe929fbf.png)

---

なぜ高度yの降順を選ばなければならないのか？極端な例を挙げて見よう。
例えば地平線の座標がこうなる場合、int[][] buildings={{1,3,3},{1,3,4},{1,3,5}};
処理済みlinesの座標：入口 [1,5],[1,4],[1,3],　出口 [3,-3],[3,-4],[3,-5]
つまり高度が3と4の地平線が完全に5に覆われている、それに入口(1)と
出口(3)のx座標も完全一致で、わざわざ同じxが持つ座標をいちいち選別して
yの最大値を探し出すには流石に面倒で、一層最初からyを降順で並べて
置き、より便利なlinesを作り上げた方がいい。もし最大高度が最初にhリストに入れないと、(1,3)(1,4),いくつか望ましくない座標が結果リストresに入ってしまう恐れがある。

---
JDKにはPairクラスが統合されていないため。
Pairクラスを使うには予めjavafx-sdkをインポートする必要がある。

```Java: TheSkylineProblem.java
public class TheSkylineProblem {

    public static void main(String[] args) {

        TheSkylineProblem solver = new TheSkylineProblem();
        // ビルに関するデータの配列をインプット。
        int[][] buildings = {{2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}};
        // 処理済みの地平線の二次元座標リスト。
        List<List<Integer>> skyline = solver.getSkyline(buildings);
        // 結果をプリントする。
        System.out.println("Skyline: " + skyline);
    }

    // 処理開始
    public List<List<Integer>> getSkyline(int[][] buildings) {

        // 結果を保存する二次元リスト
        List<List<Integer>> res = new ArrayList<>();

        // Pairクラスはvalueしか使えないMapインタフェースよりkeyも使える。
        // 処理された地平線の座標を入れるリスト。Pair<x,y>
        List<Pair<Integer, Integer>> lines = new ArrayList<>();

        // 地平線の入口の高度をプラスにし、地平線の出口の高度をマイナスにしておく。
        for (int[] a : buildings) {
            lines.add(new Pair(a[0], a[2]));
            lines.add(new Pair(a[1], -a[2]));
        }

        // linesリストをcompareメソッドで並べる
        //　Collections.sort(lines, (o1, o2) -> {　// ラムダ式、下の行と同じ効果。
         Collections.sort(lines, new Comparator<Pair<Integer, Integer>>() {
        @Override
        public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) { // 匿名内部クラス
            int x1 = o1.getKey();
            int y1 = o1.getValue();
            int x2 = o2.getKey();
            int y2 = o2.getValue();
            if (x1 != x2)
                return x1 - x2; // xが小さい方をlinesリストの前に置く（昇順）。
            else { // x1 == x2の場合
                return y2 - y1; // yが大きい方をlinesリストの前に置く（降順）。
            }
        }
        });
        // lines はこうなる [2=10, 3=15, 5=12, 7=-15, 9=-10, 12=-12, 15=10, 19=8, 20=-10, 24=-8]

        // TreeMap<Integer, Integer> h = new TreeMap<>((o1, o2) -> o2 - o1); // ラムダ式、以下と同じ効果。
        TreeMap<Integer, Integer> h = new TreeMap<>(new Comparator<Integer>() { // 匿名内部クラス
            // 降順にする。昇順でもok、ただ以下で使うfirstKey()をlastKey()に切り替える必要がある。
            // 高度の最大値を順番に取れればok。
            @Override
            public int compare(Integer o1, Integer o2) {
            // height(入れたばかりの高度) > maxHeight(TreemMapにいる最大高度)。 
                return o2 - o1;
            }
        });

        //h.put(高度y, 回数)
        h.put(0, 1); // スタート地点と隣接するビルの間を跨ぐ地平線の高さは0、
                     // 参照するため入れておいく。(12,0)->(15,0)

        for (Pair p : lines) {
            int x = (int) p.getKey();
            int height = (int) p.getValue();
            // 先ず例え同じxがある場合でも最大のyを取って置き。
            int maxHeight = h.firstKey();
            if (height > 0) {
                // xが異なる場合、入口の高度が一つ前の高度より高くなると、
                //   結果のリストに入れる。
                // もしxが同じの場合、一番高いyがまだ消されていないため、
                //   残った高度yは必ず小なるであるので、結果に入れない。
                if (height > maxHeight) {
                    res.add(new ArrayList<>(Arrays.asList(x, height)));
                }
                // 全ての入口の高度が現れた回数を入れておく、出口で消される予定。
                h.put(height, h.getOrDefault(height, 0) + 1);
            } else { // もし height(高度) < 0の場合
                // 出口の高度をプラスに変え、回数を減らすまたは消す。
                height = -height;
                Integer v = h.get(height);
                // 入れ口が一回残った場合、回数を消す。
                if (v == 1) {
                    h.remove(height);
                } else {
                    // もし同じ高度(y)を持つビルが隣り合わせているまたは
                    //   オーバーラップしている場合。
                    // 高度が降順のため、既に入口のyの回数が複数になっている。
                    //   回数を一つ減らす。
                    h.put(height, v - 1);
                }
                // もし地平線の高度が一段落ちた場合、hに残った最新の一番高い高度が
                // 削除作業の前に代入して置いたmaxHeightと異なる。
                if (maxHeight != h.firstKey()) {
                    // 元の最大高度のxが最新の最大高度と組み合わせた座標は新たな
                    // 地平線の座標となる、結果リストに入れて置く。
                    res.add(new ArrayList<>(Arrays.asList(x, h.firstKey())));
                }
            }
        }
        return res;
    }
}