1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

地平線の問題の解説

Posted at

ビルによって出来たシルエットの地平線のスタート地点の座標
(線分の左側の点)を求めること。 本文: 218問題リンク
例えばインプット(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


アプローチは全てのビルのx(縦線)を使って、水平線らと直交し、最大高度が
持つ水平線の高度yを探し出す。現在の高度yが高度リストhの最大値より高い、つまり新たな高度が見つかった場合、その座標を結果リストresに入れる。一度使われた高度は二度と使う必要がないため(お題より水平線のスタート地点の座標しかいらない)、水平線の出口高度yをマイナスにし(-は識別子の役割として、その高度からの離脱を宣言、つまり階段一段を下りる)


出口がマイナスになったlinesの座標リスト
SkylineProblemPairs.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をインポートする必要がある。

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;
    }
}
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?