ビルによって出来たシルエットの地平線のスタート地点の座標
(線分の左側の点)を求めること。 本文: 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]]。
アプローチは全てのビルのx(縦線)を使って、水平線らと直交し、最大高度が
持つ水平線の高度yを探し出す。現在の高度yが高度リストhの最大値より高い、つまり新たな高度が見つかった場合、その座標を結果リストresに入れる。一度使われた高度は二度と使う必要がないため（お題より水平線のスタート地点の座標しかいらない）、水平線の出口高度yをマイナスにし(-は識別子の役割として、その高度からの離脱を宣言、つまり階段一段を下りる)
出口がマイナスになったlinesの座標リスト
なぜ高度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をインポートする必要がある。
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;
}
}